A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming

DOI10.1007/978-3-642-29344-3_18zbMath1353.68298arXiv1109.2477OpenAlexW1637388871MaRDI QIDQ2894466

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

integer programmingshortest vector problemclosest vector problem

Mathematics Subject Classification ID

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

Related Items (8)

Covering convex bodies and the closest vector problem ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Complexity of optimizing over the integers ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ Unnamed Item ⋮ On the rational polytopes with Chvátal rank 1 ⋮ FPT-algorithm for computing the width of a simplex given by a convex hull

This page was built for publication: A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming