000163430 001__ 163430
000163430 005__ 20190316235031.0
000163430 020__ $$a978-1-4503-0682-9
000163430 02470 $$2ISI$$a000292906900053
000163430 037__ $$aCONF
000163430 245__ $$aCovering Cubes and the Closest Vector Problem
000163430 269__ $$a2011
000163430 260__ $$bAcm Order Department, P O Box 64145, Baltimore, Md 21264 Usa$$c2011
000163430 336__ $$aConference Papers
000163430 520__ $$aWe 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.
000163430 6531_ $$aclosest lattice vector problem
000163430 6531_ $$aapproximation algorithm
000163430 6531_ $$aellipsoid cover
000163430 6531_ $$abox cover
000163430 6531_ $$acovering convex bodies
000163430 700__ $$0240331$$g183121$$aEisenbrand, Friedrich
000163430 700__ $$0243824$$g188828$$aHähnle, Nicolai
000163430 700__ $$aNiemeier, Martin$$g190205$$0243825
000163430 7112_ $$dJune 13-15, 2011$$cParis, France$$a27th Annual Symposium on Computational Geometry (SoCG 2011)
000163430 773__ $$tComputational Geometry (Scg 11)$$q417-423
000163430 8564_ $$uhttps://infoscience.epfl.ch/record/163430/files/covering_1.pdf$$zn/a$$s147768
000163430 909C0 $$xU11879$$0252111$$pDISOPT
000163430 909CO $$ooai:infoscience.tind.io:163430$$qGLOBAL_SET$$pconf$$pSB
000163430 917Z8 $$x190205
000163430 917Z8 $$x190205
000163430 937__ $$aEPFL-CONF-163430
000163430 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000163430 980__ $$aCONF