TheMoneyChangingProblem(alsoknownasEqualityCon-strained Integer Knapsack Problem) is as follows: Let a1 &lt; a2 &lt; · · · &lt; akbe fixed positive integers with gcd(a1,...,ak) = 1. Given some integern, are there non-negative integers x1, . . . , xk such thati aixi = n? The Frobenius number g(a1, . . . , ak) is the largest integer n that has nodecomposition of the above form. There exist algorithms that, for fixed k, compute the Frobenius num- ber in time polynomial in logak. For variable k, one can compute a residue table of a1 words which, in turn, allows to determine the Frobe- nius number. The best known algorithm for computing the residue table has runtime O(k a1 log a1 ) using binary heaps, and O(a1 (k + log a1 )) us- ing Fibonacci heaps. In both cases, O(a1) extra memory in addition to the residue table is needed. Here, we present an intriguingly simple al- gorithm to compute the residue table in time O(k a1) and extra memory O(1). In addition to computing the Frobenius number, we can use the residue table to solve the given instance of the Money Changing Problem in constant time, for any n.

### The Money Changing Problem revisited: Computing the Frobenius number in time O(k a1)

#### Abstract

TheMoneyChangingProblem(alsoknownasEqualityCon-strained Integer Knapsack Problem) is as follows: Let a1 < a2 < · · · < akbe fixed positive integers with gcd(a1,...,ak) = 1. Given some integern, are there non-negative integers x1, . . . , xk such thati aixi = n? The Frobenius number g(a1, . . . , ak) is the largest integer n that has nodecomposition of the above form. There exist algorithms that, for fixed k, compute the Frobenius num- ber in time polynomial in logak. For variable k, one can compute a residue table of a1 words which, in turn, allows to determine the Frobe- nius number. The best known algorithm for computing the residue table has runtime O(k a1 log a1 ) using binary heaps, and O(a1 (k + log a1 )) us- ing Fibonacci heaps. In both cases, O(a1) extra memory in addition to the residue table is needed. Here, we present an intriguingly simple al- gorithm to compute the residue table in time O(k a1) and extra memory O(1). In addition to computing the Frobenius number, we can use the residue table to solve the given instance of the Money Changing Problem in constant time, for any n.
##### Scheda breve Scheda completa Scheda completa (DC)
2005
9783540280613
Money Changing Problem, combinatorics, Frobenius number, number theory, efficient algorithm
File in questo prodotto:
File
BoeckerLiptak_MoneyChangingProblem_COCOON_2005.pdf

solo utenti autorizzati

Tipologia: Versione dell'editore
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11562/391093`