More on change-making and related problems

Timothy M. Chan, Qizheng He

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Õ(t4/3), improving a previous Õ(t3/2)-time algorithm. We present a very simple Õ(u2 + 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-u2-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).

Original languageEnglish (US)
Title of host publication28th Annual European Symposium on Algorithms, ESA 2020
EditorsFabrizio Grandoni, Grzegorz Herman, Peter Sanders
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771627
DOIs
StatePublished - Aug 1 2020
Event28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy
Duration: Sep 7 2020Sep 9 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume173
ISSN (Print)1868-8969

Conference

Conference28th Annual European Symposium on Algorithms, ESA 2020
CountryItaly
CityVirtual, Pisa
Period9/7/209/9/20

Keywords

  • Coin changing
  • Dynamic programming
  • Fine-grained complexity
  • Frobenius problem
  • Knapsack

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'More on change-making and related problems'. Together they form a unique fingerprint.

Cite this