On a variant of the change-making problem
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.
Authors
- Adam N. Letchford (ORCID: https://orcid.org/0000-0002-3191-5006)
- Licong Cheng
Institutions
- Lancaster University (GB)
Publication Details
- Journal
- Operations Research Letters
- Published
- 2024-08-26
- DOI
- https://doi.org/10.1016/j.orl.2024.107165
- Primary Topic
- Constraint Satisfaction and Optimization
- Type
- article
- Field-Weighted Citation Impact
- 0.00