Exact analysis of exact change: The \(k\)-payment problem (Q2706177)

The \(k\)-payment problem is described as follows. 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 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.NEWLINENEWLINENEWLINETo obtain a complete characterization of this problem the authors prove first a necessary and sufficient condition for a given set of coins to solve the problem. Using this they show that the number of coins in any solution is at least \(kH_{N/k}\), where \(H_n\) denotes the \(n\)th partial sum of the harmonic series. Secondly, the authors give an algorithm which produces, for any given \(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)H_{N/(k+ 1)}\) coins. (Both upper and lower bounds are the best possible.) They also show how to generalize the algorithm to the case where some of the denominations are not available.