TY - CPAPER
AB - 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.
T1 - Covering Cubes and the Closest Vector Problem
DA - 2011
AU - Eisenbrand, Friedrich
AU - Hähnle, Nicolai
AU - Niemeier, Martin
JF - Computational Geometry (Scg 11)
SP - 417-423
EP - 417-423
PB - Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa
ID - 163430
KW - closest lattice vector problem
KW - approximation algorithm
KW - ellipsoid cover
KW - box cover
KW - covering convex bodies
SN - 978-1-4503-0682-9
UR - http://infoscience.epfl.ch/record/163430/files/covering_1.pdf
ER -