Frobenius problem
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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=16167
Frobenius problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Frobenius_problem&oldid=16167
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article