Exact Analysis of Exact Change: Thek-Payment Problem
Authors:
- Boaz Patt-ShamirBPBoaz Patt-Shamir
- Yiannis TsiounisYTYiannis Tsiounis
- Yair FrankelYFYair Frankel
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 13 (4) , 436-453
Abstract
We introduce the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using k disjoint subsets of the coins. The goal is to minimize the number of coins for any given N and k, while allowing the actual payments to be made on-line, namely without the need to know all payment requests in advance. The problem is motivated by the electronic cash model, where each coin is a long bit sequence, and typical electronic wallets have only limited storage capacity. The k-payment problem has additional applications in other resource-sharing scenarios. Our results include a complete characterization of the k-payment problem as follows. First, we prove a necessary and sufficient condition for a given set of coins to solve the problem. Using this characterization, we prove that the number of coins in any solution to the k-payment problem is at least k HN/k, where Hn denotes the nth element in the harmonic series. This condition can also be used to efficiently determine k (the maximal number of exact payments) which a given set of coins allows in the worst case. Secondly, we give an algorithm which produces, for any N and k, a solution with a minimal number of coins. In the case that all denominations are available, the algorithm finds a coin allocation with at most (k+1)HN/(k+1) coins. (Both upper and lower bounds are the best possible.) Finally, we show how to generalize the algorithm to the case where some of the denominations are not available.Keywords
This publication has 4 references indexed in Scilit:
- Extremal Problems in the Construction of Distributed Loop NetworksSIAM Journal on Discrete Mathematics, 1994
- Optimal bounds for the change-making problemTheoretical Computer Science, 1994
- Associate bases in the postage stamp problemJournal of Number Theory, 1992
- On the postage stamp problem with three stamp denominations, III.MATHEMATICA SCANDINAVICA, 1985