Minkowski's Convex Body Theorem and Integer Programming

1 August 1987

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research

Vol. 12 (3) , 415-440
https://doi.org/10.1287/moor.12.3.415

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.

Keywords

This publication has 0 references indexed in Scilit: