Minkowski's Convex Body Theorem and Integer Programming

TLDR

Minkowski's Convex Body theorem and other Geometry of Numbers results underpin the algorithm. The paper presents an algorithm for solving Integer Programming problems with running time n O(n) and introduces related lattice‑problem algorithms. The algorithm reduces an n‑variable problem to (2n)^{5i/2} subproblems in n−i variables, with i chosen by the algorithm, and analyzes their complexity under polynomial‑time reductions. The algorithm achieves an O(n^{5/2}) per‑variable factor, improving on the previous exponential bound.

Abstract

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