Advertisement
Published in:
2012 | OriginalPaper | Chapter
A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming
Author : Daniel Dadush
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The Integer Programming Problem (IP) for a polytope
P
⊆ ℝ
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
O
(1/
ε
2
)
n
-time and
O
(1/
ε
)
n
-space with overwhelming probability. We reduce this approximate IP question to an approximate Closest Vector Problem (CVP) in a “near-symmetric” semi-norm, which we solve via a randomized sieving technique first developed by Ajtai, Kumar, and Sivakumar (STOC 2001). Our main technical contribution is an extension of the AKS sieving technique which works for any near-symmetric semi-norm. Our results also extend to general convex bodies and lattices.