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
Article number107165
<mark>Journal publication date</mark>30/11/2024
<mark>Journal</mark>Operations Research Letters
Volume57
Number of pages3
Publication StatusPublished
Early online date29/08/24
<mark>Original language</mark>English

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.