Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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
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.
