zbMATH — the first resource for mathematics

Minkowski’s convex body theorem and integer programming. (English) Zbl 0639.90069
The paper presents an algorithm for solving integer programming problems whose running time depends on the number n of variables as \(n^{O(n)}\). This is done by reducing an n variable problem to \((2n)^{5i/2}\) problems in n-i variables for some i greater than zero chosen by the algorithm. The factor of \(O(n^{5/2})\) “per variable” improves the best previously known factor which is exponential in n. Minkowski’s Convex Body theorem and other results from the geometry of numbers play a crucial role in the algorithm. Several related algorithms for lattice problems are presented. The complexity of these problems with respect to polynomial-time reducibilities is studied.

90C10 Integer programming
52Bxx Polytopes and polyhedra
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI