𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimal bounds for the change-making problem

✍ Scribed by Dexter Kozen; Shmuel Zaks

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
681 KB
Volume
123
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Optimal Bounds for the Predecessor Probl
Optimal Bounds for the Predecessor Problem and Related Problems
✍ Paul Beame; Faith E. Fich πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 269 KB

We obtain matching upper and lower bounds for the amount of time to find the predecessor of a given element among the elements of a fixed compactly stored set. Our algorithms are for the unit-cost word RAM with multiplication and are extended to give dynamic algorithms. The lower bounds are proved f

An optimal lower bound for the Frobenius
An optimal lower bound for the Frobenius problem
✍ Iskander M. Aliev; Peter M. Gruber πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 127 KB

Given N 2 positive integers a 1 , a 2 , . . . , a N with GCD(a 1 , . . . , a N ) = 1, let f N denote the largest natural number which is not a positive integer combination of a 1 , . . . , a N . This paper gives an optimal lower bound for f N in terms of the absolute inhomogeneous minimum of the sta