Change-making problems revisited: a parameterized point of view

Steffen Goebbels (), Frank Gurski (), Jochen Rethmann () and Eda Yilmaz ()
Additional contact information
Steffen Goebbels: Niederrhein University of Applied Sciences
Frank Gurski: University of Düsseldorf
Jochen Rethmann: Niederrhein University of Applied Sciences
Eda Yilmaz: University of Düsseldorf

Journal of Combinatorial Optimization, 2017, vol. 34, issue 4, No 15, 1218-1236

Abstract: Abstract The change-making problem is the problem of representing a given amount of money with the fewest number of coins possible from a given set of coin denominations. In the general version of the problem, an upper bound for the availability of every coin value is given. Even the special case, where for each value an unlimited number of coins is available, is NP-hard. Since in the original problem some amounts can not be represented, especially if no coin of value one exists, we introduce generalized problems that look for approximations of the given amount such that a cost function is minimized. We recall algorithms for the change-making problem and present new algorithms for the generalized version of the problem. Motivated by the NP-hardness we study fixed-parameter tractability of all these problems. We show that some of these problems are fixed-parameter tractable and that some are $$\hbox {W}[1]$$ W [ 1 ] -hard. In order to show the existence of polynomial and constant-size kernels we prove some general results and apply them to several parameterizations of the change-making problems.

Keywords: Fixed-parameter tractability; Kernelization; Combinatorial optimization; 90C39; 68R05; 68Q25 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0143-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:4:d:10.1007_s10878-017-0143-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0143-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().