Difference between revisions of "Frobenius problem"
From Encyclopedia of Mathematics
(Importing text file) |
(MSC 11D07) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | {{TEX|done}}{{MSC|11D07}} | ||
| + | |||
''coin-change problem'' | ''coin-change problem'' | ||
| − | Given | + | 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 | + | 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 | + | For a fixed $n$ there is a polynomial-time algorithm to solve the Frobenius problem, [[#References|[a1]]]. |
| − | The Frobenius problem is related to the study of maximal lattice-point-free convex bodies (in the [[ | + | The Frobenius problem is related to the study of maximal lattice-point-free convex bodies (in the [[geometry of numbers]]), [[#References|[a2]]]. |
====References==== | ====References==== | ||
| − | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> R. Kannan, "Lattice translates of a polytope and the Frobenius problem" ''Combinatorica'' , '''12''' (1992) pp. 161–172</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> L. Lovász, "Geometry of numbers and integer programming" M. Iri (ed.) K. Tanabe (ed.) , ''Mathematical Programming'' , Kluwer Acad. Publ. (1989) pp. 177–202</TD></TR></table> | + | <table> |
| + | <TR><TD valign="top">[a1]</TD> <TD valign="top"> R. Kannan, "Lattice translates of a polytope and the Frobenius problem" ''Combinatorica'' , '''12''' (1992) pp. 161–172</TD></TR> | ||
| + | <TR><TD valign="top">[a2]</TD> <TD valign="top"> L. Lovász, "Geometry of numbers and integer programming" M. Iri (ed.) K. Tanabe (ed.) , ''Mathematical Programming'' , Kluwer Acad. Publ. (1989) pp. 177–202</TD></TR> | ||
| + | </table> | ||
Latest revision as of 21:17, 8 April 2018
2020 Mathematics Subject Classification: Primary: 11D07 [MSN][ZBL]
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 $n$ 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