Frobenius problem

From Encyclopedia of Mathematics
Revision as of 17:15, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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].


[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:
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article