13
$\begingroup$

Given $n$ coin denominations, with $c_1=1$ and $c_2<c_3<..<c_{n}$ being random numbers uniformly distributed in the range $[2,N]$. Asymptotically, for what fraction of coins does the greedy algorithm generate optimal change using this set of denominations?

The answer is known for 3 denominations ; but what about the general case?

$\endgroup$
  • 2
    $\begingroup$ Establishing the probability for 4 denominations was posed by Thane Plambeck, who also provided an expression for the probability for 3 denominations (see the link provided by the OP). The OP is asking a more general question about the asymptotic behaviour of this probability. This might perhaps be more suitable for math.SE and MO, with tag asymptotics. @Ganesh: What is your TCS motivation, or the reason for the ds.algorithms tag? $\endgroup$ – András Salamon Apr 5 '11 at 10:37
  • 1
    $\begingroup$ @ Andras, this is very much a complexity theory problem. For instance ,if the greedy approach gets optimal solution say 90% of the time, I may as well forget dynamic programming and settle for suboptimal solutions the remaining 10% of the time. Maybe this is more appropriate at Math.*, but the motivation lies in TCS. Finally,the "right tag" escaped me - so I thought that ds.algorithms was the best approximation. $\endgroup$ – Ganesh Apr 5 '11 at 19:44
9
$\begingroup$

This is not an answer but maybe this will point you or someone else in the right direction.

I found the paper by D. Kozen and S. Zaks called "Optimal Bounds for the Change-Making Problem" wherein they give conditions for when a coin change instance's greedy change making algorithm is optimal. I will use their notation.

Given a coin change instance of $m$ distinct coins $$ ( c_1, c_2, c_3, \cdots, c_{m-1}, c_{m} ) $$ $$ c_1 = 1 < c_2 < c_3 < \cdots < c_{m-1} < c_m $$ a function $M(x)$ representing the optimal number of coins needed to make change for $x$ and a function $G(x)$ representing the number of coins needed to greedily make change for $x$, then if $M(x) \ne G(x)$, there exists a counterexample in the range $$ c_3 + 1 < x < c_{m-1} + c_m $$

They go on to show that

If for every $x$ in the range $c_3 + 1 < x < c_{m-1} + c_m $ $$ G(x) \le G(x-c) + 1$$ $$ c \in (c_1, c_2, \cdots, c_m )$$ then $G(x) = M(x)$ (i.e. the greedy algorithm is the optimal).

This gives us an "efficient" (up to pseudo polynomial time) test to determine whether a coin change instance is greedy or not.

Using the above, I have run a short simulation the results of which are plotted on a log-log scale below

enter image description here

Each point represents the average of 10000 instance creations for $m$ shown and each element chosen to be distinct but otherwise uniform and at random from the range of $[1 \cdots N]$.

Given that we know the probability of the greedy algorithm being optimal for $m=3$ goes as $\frac{8}{3} N^{-\frac{1}{2}}$, from just looking at the graph I would hazard a guess that the probability of the greedy algorithm being optimal goes as:

$$ p_m(N) \propto N^{-\frac{(m-2)}{2} } $$

where $p_m(N)$ is the probability that $m$ distinct coins drawn uniformly at random from the range of $N$ is greedy optimal (otherwise known as 'canonical').

In the large $m$ limit, the probability that the greedy solution is optimal goes quickly to 0 for any non-trivial value of $N$. If the above equation holds, then it is easy to see, but there might be other ways of looking at it that give the same conclusion. For example, looking at Borgs, Chayes, Mertens and Nair's Random Energy Model work indicate that the energy is too jagged at the bottom to expect local moves (i.e. greedy moves) to give an optimal solution. This is of course for the Number Partition Problem and is only provided to give some intuition rather than a definite answer.

At the risk of answering a question that you did not ask, I wanted to point out that "real world" coin systems do not follow a uniform distribution for coin denominations. For example, the USA has at least 12 denominations (including bills: $ (1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$ ) which do not appear to be uniformly distributed. Perhaps looking at other distributions to generate the coin denominations would yield non-trivial results in the large system limit. For example, a power law distribution might yield coin denominations that are more similar to the USA's.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.