DocumentCode :
2263701
Title :
Exact analysis of exact change
Author :
Frankel, Yair ; Patt-Shamir, Boaz ; Tsiounis, Yiannis
Author_Institution :
Sandia Nat. Labs., Livermore, CA, USA
fYear :
1997
fDate :
17-19 Jun 1997
Firstpage :
107
Lastpage :
118
Abstract :
We consider 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 kHN 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 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 :
EFTS; budgeting; computational complexity; dynamic programming; minimisation; resource allocation; EFTS; budget; coin allocation; coins; disjoint subsets; dynamic programming; electronic cash model; electronic wallets; exact analysis; exact change; harmonic series; k-payment problem; limited storage capacity; long bit sequence; lower bounds; online payments; resource-sharing; upper bounds; Bandwidth; Computer science; Contracts; Educational institutions; Laboratories; Processor scheduling; Resource management;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location :
Ramat-Gan
Print_ISBN :
0-8186-8037-7
Type :
conf
DOI :
10.1109/ISTCS.1997.595162
Filename :
595162
Link To Document :
بازگشت