Home > Covering Cubes and the Closest Vector Problem > HTML MARC |

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