Lattice translates of a polytope and the Frobenius problem (Q1196686)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 89342
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Lattice translates of a polytope and the Frobenius problem |
scientific article; zbMATH DE number 89342 |
Statements
Lattice translates of a polytope and the Frobenius problem (English)
0 references
16 January 1993
0 references
Given \(n\) coprime natural numbers \(a_ 1,a_ 2,\ldots,a_ n\) the Frobenius problem of finding the largest natural number not expressible as \(a_ 1x_ 1+a_ 2x_ 2+\cdots+a_ nx_ n\) with nonnegative \(x_ 1,x_ 2,\ldots,x_ n\) is an \(NP\)-hard problem. By using some recent results in the Geometry of Numbers a polynomial time algorithm for every fixed \(n\) is given.
0 references
covering radius
0 references
polytope
0 references
lattice translates
0 references
Frobenius problem
0 references
polynomial time algorithm
0 references
0.89894223
0 references
0.89342844
0 references
0.8906015
0 references
0.88543034
0 references
0.8853137
0 references
0 references
0.8840827
0 references
