Exact analysis of exact change

        	Yair Frankel (CERTCO, NY, NY)
	Boaz Patt-Shamir (Northeastern University, Boston, MA)
        Yiannis Tsiounis (GTE Labs, Waltham MA. Research performed
	while at Northeastern University, Boston, MA)

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 k H_{N/k}, where H_n 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)H_{N/(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.