Geodesic
Totally greedy coin sets and greedy obstructions
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A coin set is a strictly increasing list of positive integers that always begins with 1. A coin set is called greedy when the simple greedy change-making algorithm always produces the fewest number of coins in change. Here, the greedy change-making algorithm repeatedly selects the largest denomination coin less than the remaining amount until it has assembled the correct change. Pearson has provided an efficient algorithm for determining whether a coin set is greedy. We study a stricter property on coin sets, called total greediness, which requires that all initial subsequences of the coin set also be greedy, and a simple property makes it easy to test if a coin set is totally greedy. We begin to explore the theory of greedy obstructions– those coin sets that cannot be extended to greedy coin sets by the addition of coins in larger denominations.
DOI : 10.37236/814
Classification : 05A99, 68R05, 90C27
Mots-clés : coin set, greedy coin set, change making algorithm, total greediness, initial subsequences, greedy obstructions, denominations 
@article{10_37236_814,
     author = {L. J. Cowen and Robert Cowen and Arthur Steinberg},
     title = {Totally greedy coin sets and greedy obstructions},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/814},
     zbl = {1165.05314},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/814/}
}
TY  - JOUR
AU  - L. J. Cowen
AU  - Robert Cowen
AU  - Arthur Steinberg
TI  - Totally greedy coin sets and greedy obstructions
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/814/
DO  - 10.37236/814
ID  - 10_37236_814
ER  - 
%0 Journal Article
%A L. J. Cowen
%A Robert Cowen
%A Arthur Steinberg
%T Totally greedy coin sets and greedy obstructions
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/814/
%R 10.37236/814
%F 10_37236_814
L. J. Cowen; Robert Cowen; Arthur Steinberg. Totally greedy coin sets and greedy obstructions. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/814

Cité par Sources :