Home > Research > Publications & Outputs > On a variant of the change-making problem

Research

Associated organisational unit

Electronic data

  • change-making

    Accepted author manuscript, 289 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

On a variant of the change-making problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On a variant of the change-making problem. / Letchford, Adam; Cheng, Licong.
In: Operations Research Letters, Vol. 57, 107165, 30.11.2024.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, A & Cheng, L 2024, 'On a variant of the change-making problem', Operations Research Letters, vol. 57, 107165. https://doi.org/10.1016/j.orl.2024.107165

APA

Letchford, A., & Cheng, L. (2024). On a variant of the change-making problem. Operations Research Letters, 57, Article 107165. https://doi.org/10.1016/j.orl.2024.107165

Vancouver

Letchford A, Cheng L. On a variant of the change-making problem. Operations Research Letters. 2024 Nov 30;57:107165. Epub 2024 Aug 29. doi: 10.1016/j.orl.2024.107165

Author

Letchford, Adam ; Cheng, Licong. / On a variant of the change-making problem. In: Operations Research Letters. 2024 ; Vol. 57.

Bibtex

@article{a467e0b4c9164ae7b7b26f23e01172d0,
title = "On a variant of the change-making problem",
abstract = "The change-making problem (CMP), introduced in 1970, is a classic problem in combinatorial optimisation. It was proven to be NP-hard in 1975, but it can be solved in pseudo-polynomial time by dynamic programming. In 1999, Heipcke presented a variant of the CMP which, at first glance, looks harder than the standard version. We show that, in fact, her variant can be solved in polynomial time.",
keywords = "knapsack problems, combinatorial optimisation",
author = "Adam Letchford and Licong Cheng",
year = "2024",
month = nov,
day = "30",
doi = "10.1016/j.orl.2024.107165",
language = "English",
volume = "57",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On a variant of the change-making problem

AU - Letchford, Adam

AU - Cheng, Licong

PY - 2024/11/30

Y1 - 2024/11/30

N2 - The change-making problem (CMP), introduced in 1970, is a classic problem in combinatorial optimisation. It was proven to be NP-hard in 1975, but it can be solved in pseudo-polynomial time by dynamic programming. In 1999, Heipcke presented a variant of the CMP which, at first glance, looks harder than the standard version. We show that, in fact, her variant can be solved in polynomial time.

AB - The change-making problem (CMP), introduced in 1970, is a classic problem in combinatorial optimisation. It was proven to be NP-hard in 1975, but it can be solved in pseudo-polynomial time by dynamic programming. In 1999, Heipcke presented a variant of the CMP which, at first glance, looks harder than the standard version. We show that, in fact, her variant can be solved in polynomial time.

KW - knapsack problems

KW - combinatorial optimisation

U2 - 10.1016/j.orl.2024.107165

DO - 10.1016/j.orl.2024.107165

M3 - Journal article

VL - 57

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

M1 - 107165

ER -