Totally greedy coin sets (2008)

Originators: Lenore Cowen, Robert Cowen, and Arthur Steinberg    (presented by Jane Butterfield - REGS 2008)

Definitions: A coinset is a set {a₁,...,a_k} of positive integers such that 1 = a₁ < ... < a_k; the elements are called denominations. Let N[C;y] denote the minimum number of coins with denominations in C needed to sum to y. Let G[C;y] denote the number of coins with denominations in C that a greedy algorithm selects to sum to y, always choosing the largest denomination that does not put the total above y.

A coinset C is greedy if N[C;y] = G[C;y] for every positive integer y. A coinset C is totally greedy if every initial segment {1,a₂,...,a_j} of C is greedy. A coinset is ultra-greedy if every subset of it containing the element 1 is greedy. A non-greedy coinset C is an obstruction if every extension of C by appending numbers larger than its largest element a_k is not greedy. If G[C;y]>N[C;y] for some y less than a_k, then C is a trivial obstruction.

Comments: The coinset consisting of the first k odd numbers is totally greedy. The coinset consisting of the first k powers of a constant a is ultra-greedy. Initial segments of the Fibonacci sequence are totally greedy but not ultra-greedy. Cowen, Cowen, and Steinberg [CCS] proved that every non-greedy coinset of size 3 is an obstruction.

Question 1: Which coinsets with more than three denominations are nontrivial obstructions? Which among those of size 4?

Question 2: Which greedy coinsets are totally greedy?

Question 3: Are there any large ultra-greedy coinsets that do not consist of powers of a fixed integer?

Comments: Pearson [P] devised an algorithm to determine whether a given coinset is greedy. Cowen, Cowen, and Steinberg [CCS] found a shorter algorithm to determine whether a given coinset is totally greedy. Characterizing those coinsets that are greedy but not totally greedy would extend this shorter algorithm to replace Pearson's. Kozen and Zaks [KZ] showed that if C is not greedy, then N[C;y]≠G[C;y] for some y with a₃+1<y<a_k+a_k-1. [CCS] presents a criterion for extending a greedy coinset (leading to the algorithm mentioned above: If C is greedy and C' is obtained from C by appending the value a_k+1, then C' is greedy if and only if G[C';ma_k]≤m, where m=⌈a_k+1/a_k⌉.

References:
[CCS] L. Cowen, R. Cowen, A. Steinberg; Totally greedy coin sets and greedy obstructions. Electr. J. Combin. 15 (2008), Paper R90, 13 pages.
[KZ] Kozen, Dexter; Zaks, Shmuel; Optimal bounds for the change-making problem. Theoret. Comput. Sci. 123 (1994), no. 2, 377--388.
[P] D. Pearson; A polynomial time algorithm for the change-making problem. Operations Research Letters, 33(3):231-234, 2005.