## 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 : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings. Wang L (Ed); Lecture Notes in Computer Science, 3595. Berlin: Springer: 965-974.

Konferenzbeitrag | Veröffentlicht | Englisch

Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Böcker, Sebastian; Lipták, ZsuzsannaUniBi
Herausgeber*in
Wang, Lusheng
Einrichtung
Abstract / Bemerkung
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.
Erscheinungsjahr
2005
Titel des Konferenzbandes
Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings
Serien- oder Zeitschriftentitel
Lecture Notes in Computer Science
Band
3595
Seite(n)
965-974
ISBN
978-3-540-28061-3
ISSN
0302-9743
Page URI
https://pub.uni-bielefeld.de/record/1601976

## Zitieren

Böcker S, Lipták Z. The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1)). In: Wang L, ed. Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings. Lecture Notes in Computer Science. Vol 3595. Berlin: Springer; 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)). In L. Wang (Ed.), Lecture Notes in Computer Science: Vol. 3595. Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings (pp. 965-974). Berlin: Springer. https://doi.org/10.1007/11533719_97
Böcker, Sebastian, and Lipták, Zsuzsanna. 2005. “The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1))”. In Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings, ed. Lusheng Wang, 3595:965-974. Lecture Notes in Computer Science. Berlin: Springer.
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 : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings, Wang, L. ed. Lecture Notes in Computer Science, vol. 3595, (Berlin: Springer), 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 L. Wang, ed. Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings. Lecture Notes in Computer Science. no.3595 Berlin: Springer, 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 : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings, L. Wang, ed., Lecture Notes in Computer Science, vol. 3595, Berlin: Springer, 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)). In: Wang, L. (ed.) Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings. Lecture Notes in Computer Science. 3595, p. 965-974. Springer, Berlin (2005).
Böcker, Sebastian, and Lipták, Zsuzsanna. “The Money Changing Problem revisited: Computing the Frobenius number in time O(k a(1))”. Computing and Combinatorics : 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005, Proceedings. Ed. Lusheng Wang. Berlin: Springer, 2005.Vol. 3595. Lecture Notes in Computer Science. 965-974.
Export

Open Data PUB

### Web of Science

Dieser Datensatz im Web of Science®
Suchen in