A O(1/ ^2)^n -time sieving algorithm for approximate integer programming

DOI10.1007/978-3-642-29344-3_18MaRDI QIDQ2894466zbMATH OpenOpenAlexFDO

Authors Daniel Dadush

Publication date 29 June 2012

Published in LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.2477

zbMATH Keywords

closest vector probleminteger programmingshortest vector problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Integer programming (90C10)

Abstract: The Integer Programming Problem (IP) for a polytope P subseteq R^n is to find an integer point in P or decide that P is integer free. We give an algorithm for an approximate version of this problem, which correctly decides whether P contains an integer point or whether a (1+eps) scaling of P around its barycenter is integer free in time O(1/eps^2)^n. We reduce this approximate IP question to an approximate Closest Vector Problem (CVP) in a "near-symmetric" semi-norm, which we solve via a 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.

Recommendations

• A randomized sieving algorithm for approximate integer programming
• Some sieving algorithms for lattice problems
• A sieve algorithm for the shortest lattice vector problem
• Minkowski's Convex Body Theorem and Integer Programming
• scientific article; zbMATH DE number 6607548

Cited in

(10)

• Covering convex bodies and the closest vector problem
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
• On the rational polytopes with Chvátal rank 1
• FPT-algorithm for computing the width of a simplex given by a convex hull
• On the complexity of quasiconvex integer minimization problem
• A randomized sieving algorithm for approximate integer programming
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• Centerpoints: a link between optimization and convex geometry
• Complexity of optimizing over the integers
• Minimizing convex functions with rational minimizers

This page was built for publication: A \(O(1/\epsilon ^{2})^{n }\)-time sieving algorithm for approximate integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894466)