Covering cubes and the closest vector problem

DOI10.1145/1998196.1998264MaRDI QIDQ5404456zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier

Publication date 24 March 2014

Published in Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.2289, https://infoscience.epfl.ch/record/163430/files/covering_1.pdf

zbMATH Keywords

approximation algorithmellipsoid covercovering convex bodiesbox coverclosest lattice vector problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^O(n) (log 1/epsilon)^O(n)$ which improves upon the (2+1/epsilon)^O(n) running time of the previously best algorithm by Bl"omer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon in (0,1), how many ellipsoids are necessary to cover the cube [-1+epsilon, 1-epsilon]^n such that all ellipsoids are contained in the standard unit cube [-1,1]^n? We provide an almost optimal bound for the case where the ellipsoids are restricted to be axis-parallel. We then apply our covering scheme to a variation of this covering problem where one wants to cover [-1+epsilon,1-epsilon]^n with parallelepipeds that, if scaled by two, are still contained in the unit cube. Thereby, we obtain a method to boost any 2-approximation algorithm for closest-vector in the infinity norm to a (1+epsilon)-approximation algorithm that has the desired running time.

Recommendations

• Covering convex bodies and the closest vector problem
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• scientific article; zbMATH DE number 6607548
• Lattice sparsification and the approximate closest vector problem

Cited in

(16)

• Covering the cube by affine hyperplanes
• A note on the minimal volume of almost cubic parallelepipeds
• Economical convex coverings and applications
• scientific article; zbMATH DE number 7561389 (Why is no real title available?)
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• FPT-algorithms for some problems related to integer programming
• Approximate CVP_p in Time 2^{0.802 n}
• Algorithms for the shortest and closest lattice vector problems
• Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• Covering convex bodies and the closest vector problem
• From approximate to exact integer programming
• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
• Efficient quantisation and weak covering of high dimensional cubes
• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• A randomized sieving algorithm for approximate integer programming
• On the complexity of quasiconvex integer minimization problem

This page was built for publication: Covering cubes and the closest vector problem

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