License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.29
URN: urn:nbn:de:0030-drops-128958
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12895/
Chan, Timothy M. ;
He, Qizheng
More on Change-Making and Related Problems
Abstract
Given a set of n integer-valued coin types and a target value t, the well-known change-making problem asks for the minimum number of coins that sum to t, assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j, for every j = 0,…,t. For example, the textbook dynamic programming algorithms can solve the all-targets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version.
In this paper, we obtain a number of new results on change-making and related problems:
- We present a new algorithm for the all-targets change-making problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})-time algorithm.
- We present a very simple Õ(u²+t)-time algorithm for the all-targets change-making problem, where u denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by u).
- For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)).
- For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous near-u²-time algorithms.
- We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case).
BibTeX - Entry
@InProceedings{chan_et_al:LIPIcs:2020:12895,
author = {Timothy M. Chan and Qizheng He},
title = {{More on Change-Making and Related Problems}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {29:1--29:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12895},
URN = {urn:nbn:de:0030-drops-128958},
doi = {10.4230/LIPIcs.ESA.2020.29},
annote = {Keywords: Coin changing, knapsack, dynamic programming, Frobenius problem, fine-grained complexity}
}
|
Keywords: |
|
Coin changing, knapsack, dynamic programming, Frobenius problem, fine-grained complexity |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
