A Randomized Sieving Algorithm for Approximate Integer Programming

The Integer Programming Problem (IP) for a polytope \(P \subseteq \mathbb{R} ^{n}\) is to find an integer point in P or decide that P is integer free. We give a randomized algorithm for an approximate version of this problem, which correctly decides whether P contains an integer point or whether a (1+?)-scaling of P about its center of gravity is integer free in 2 ^O(n)(1/? ²) ⁿ -time and 2 ^O(n)(1/?) ⁿ -space with overwhelming probability. Our algorithm proceeds by reducing the approximate IP problem to an approximate Closest Vector Problem (CVP) under a “near-symmetric” norm. Our main technical contribution is an extension of the AKS randomized sieving technique, first developed by Ajtai et al. (Proceedings of 33rd Symposium on the Theory of Computing (STOC), pp. 601–610, 2001) for lattice problems under the ? ₂ norm, to the setting of asymmetric norms. We also present an application of our techniques to exact IP, where we give a nearly optimal algorithmic implementation of the Flatness Theorem, a central ingredient for many IP algorithms. Our results also extend to general convex bodies and lattices.