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

Böcker S, Lipták Z (2005)
In: COMPUTING AND COMBINATORICS, PROCEEDINGS. 3595. SPRINGER-VERLAG BERLIN: 965-974.

Conference Paper | Published | English

No fulltext has been uploaded

Author
Abstract
The Money Changing Problem (also known as Equality Constrained Integer Knapsack Problem) is as follows: Let a1 < a2 < (...) < a(k) be fixed positive integers with gcd(a(1),...,a(k)) = 1. Given some integer n, are there non-negative integers chi(1),...,chi(k) such that Sigma(i)a(i)x(i) = n? The Frobenius number g(a(1),...,ak) is the largest integer n that has no decomposition of the above form. There exist algorithms that, for fixed k, compute the Frobenius number in time polynomial in log a(k). For variable k, one can compute a residue table of a, words which, in turn, allows to determine the Frobenius number. The best known algorithm for computing the residue table has runtime O(ka(1), log a(1)) using binary heaps, and O(a(1) (k + log a(1))) using Fibonacci heaps. In both cases, O(a(1)) extra memory in addition to the residue table is needed. Here, we present an intriguingly simple algorithm to compute the residue table in time O(k a(1)) 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.
Publishing Year
ISSN
PUB-ID

Cite this

Böcker S, Lipták Z. The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1)). In: COMPUTING AND COMBINATORICS, PROCEEDINGS. Vol 3595. SPRINGER-VERLAG BERLIN; 2005: 965-974.
Böcker, S., & Lipták, Z. (2005). The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1)). COMPUTING AND COMBINATORICS, PROCEEDINGS, 3595, 965-974.
Böcker, S., and Lipták, Z. (2005). “The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1))” in COMPUTING AND COMBINATORICS, PROCEEDINGS, vol. 3595, (SPRINGER-VERLAG BERLIN), 965-974.
Böcker, S., & Lipták, Z., 2005. The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1)). In COMPUTING AND COMBINATORICS, PROCEEDINGS. no.3595 SPRINGER-VERLAG BERLIN, pp. 965-974.
S. Böcker and Z. Lipták, “The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1))”, COMPUTING AND COMBINATORICS, PROCEEDINGS, vol. 3595, SPRINGER-VERLAG BERLIN, 2005, pp.965-974.
Böcker, S., Lipták, Z.: The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1)). COMPUTING AND COMBINATORICS, PROCEEDINGS. 3595, p. 965-974. SPRINGER-VERLAG BERLIN (2005).
Böcker, S, and Lipták, Zsuzsanna. “The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1))”. COMPUTING AND COMBINATORICS, PROCEEDINGS. SPRINGER-VERLAG BERLIN, 2005.Vol. 3595. 965-974.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar