163430
20190316235031.0
978-1-4503-0682-9
ISI
000292906900053
CONF
Covering Cubes and the Closest Vector Problem
2011
Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa
2011
Conference Papers
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ömer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon>0, how many ellipsoids are necessary to cover the scaled unit cube [-1+epsilon, 1-epsilon]^n such 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 the scaled cube with boxes 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.
closest lattice vector problem
approximation algorithm
ellipsoid cover
box cover
covering convex bodies
240331
Eisenbrand, Friedrich
183121
243824
Hähnle, Nicolai
188828
243825
Niemeier, Martin
190205
27th Annual Symposium on Computational Geometry (SoCG 2011)
Paris, France
June 13-15, 2011
417-423
Computational Geometry (Scg 11)
147768
http://infoscience.epfl.ch/record/163430/files/covering_1.pdf
n/a
252111
DISOPT
U11879
oai:infoscience.tind.io:163430
conf
SB
GLOBAL_SET
190205
190205
EPFL-CONF-163430
EPFL
REVIEWED
PUBLISHED
CONF