-
- Ravi Kannan
- Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213
説明
<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>
収録刊行物
-
- Mathematics of Operations Research
-
Mathematics of Operations Research 12 (3), 415-440, 1987-08
Institute for Operations Research and the Management Sciences (INFORMS)
