Minkowski's Convex Body Theorem and Integer Programming

DOI Web Site 25 Citations
  • Ravi Kannan
    Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213

Description

<jats:p> The paper presents an algorithm for solving Integer Programming problems whose running time depends on the number n of variables as n<jats:sup>O(n)</jats:sup>. This is done by reducing an n variable problem to (2n)<jats:sup>5i/2</jats:sup> problems in n − i variables for some i greater than zero chosen by the algorithm. The factor of O(n<jats:sup>5/2</jats:sup>) “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. </jats:p>

Journal

Citations (25)*help

See more

Details 詳細情報について

Report a problem

Back to top