A polynomial-time algorithm for the change-making problem

DOI10.1016/j.orl.2004.06.001zbMath1177.90350OpenAlexW2001816150MaRDI QIDQ1779695

Niranjan Chakravarthy

Publication date: 1 June 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6219

zbMATH Keywords

Greedy algorithmChange-makingCoin systems

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Greedy routing in circulant networks ⋮ What's in \textit{YOUR} wallet? ⋮ Unnamed Item ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Fractal patterns related to dividing coins ⋮ Change-making problems revisited: a parameterized point of view ⋮ When greedy gives optimal: a unified approach ⋮ Characterization of canonical systems with six types of coins for the change-making problem ⋮ Research and development of fringe projection-based methods in 3D shape reconstruction ⋮ Combinatorics of the change-making problem

Cites Work

• Unnamed Item
• Optimal bounds for the change-making problem
• Algorithmic Solution of the Change-Making Problem