Namespaces
Variants
Actions

Difference between revisions of "Frobenius problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''coin-change problem''
 
''coin-change problem''
  
Given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102001.png" /> natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102002.png" /> with greatest common divisor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102003.png" />, find the largest natural number that is not expressible as a linear non-negative integer combination of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102004.png" />.
+
Given $n$ natural numbers $a_1,\ldots,a_n$ with greatest common divisor $1$, find the largest natural number that is not expressible as a linear non-negative integer combination of the $a_1,\ldots,a_n$.
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102005.png" /> the answer is given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102006.png" />. The general problem is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102008.png" />-hard.
+
For $n=2$ the answer is given by $a_1a_2-a_1-a_2$. The general problem is $\mathcal{NP}$-hard.
  
 
For a fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102009.png" /> there is a polynomial-time algorithm to solve the Frobenius problem, [[#References|[a1]]].
 
For a fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f110/f110200/f1102009.png" /> there is a polynomial-time algorithm to solve the Frobenius problem, [[#References|[a1]]].

Revision as of 15:25, 10 August 2014

coin-change problem

Given $n$ natural numbers $a_1,\ldots,a_n$ with greatest common divisor $1$, find the largest natural number that is not expressible as a linear non-negative integer combination of the $a_1,\ldots,a_n$.

For $n=2$ the answer is given by $a_1a_2-a_1-a_2$. The general problem is $\mathcal{NP}$-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
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article