Covering Cubes and the Closest Vector Problem

Details Covering Cubes and the Closest Vector Problem Covering Cubes and the Closest Vector Problem

2010-12-10

arxiv.org/abs/1012.2289v1

Computer Science

Data Structures and Algorithms

Scientific paper

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\"omer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon in (0,1), how many ellipsoids are necessary to cover the cube [-1+epsilon, 1-epsilon]^n such that 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 [-1+epsilon,1-epsilon]^n with parallelepipeds 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.

Affiliated with

Also associated with

No associations

Rating

Covering Cubes and the Closest Vector Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Covering Cubes and the Closest Vector Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Covering Cubes and the Closest Vector Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107956