Covering cubes and the closest vector problem
Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier · 2011
We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest lattice 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.