Frobenius problem
From Encyclopedia of Mathematics
coin-change problem
Given 
natural numbers 
with greatest common divisor 
, find the largest natural number that is not expressible as a linear non-negative integer combination of the 
.
For 
the answer is given by 
. The general problem is 
-hard.
For a fixed 
there is a polynomial-time algorithm to solve the Frobenius problem, [a1].
The Frobenius problem is related to the study of maximal lattice-point-free convex bodies (in the geometry of numbers), [a2].
References
| [a1] | R. Kannan, "Lattice translates of a polytope and the Frobenius problem" Combinatorica , 12 (1992) pp. 161–172 |
| [a2] | L. Lovász, "Geometry of numbers and integer programming" M. Iri (ed.) K. Tanabe (ed.) , Mathematical Programming , Kluwer Acad. Publ. (1989) pp. 177–202 |
How to Cite This Entry:
Frobenius problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Frobenius_problem&oldid=32825
Frobenius problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Frobenius_problem&oldid=32825
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article