Economical Convex Coverings and Applications
share
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ϵ> 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ϵ expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ϵ-kernels of point sets, approximate nearest neighbor searching, polytope approximations, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size n^O(n) / ϵ^(n-1)/2 for general convex bodies in R^n. In special cases, such as when the convex body is the ℓ_p unit ball, this bound has been improved to 2^O(n) / ϵ^(n-1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, under the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter ϵ> 0, we show that there exists a polytope P consisting of 2^O(n) / ϵ^(n-1)/2 vertices (facets) such that K ⊂ P ⊂ K(1+ϵ). This bound is optimal in the worst case up to factors of 2^O(n). As an additional consequence, we obtain the fastest (1+ϵ)-approximate CVP algorithm that works in any norm, with a running time of 2^O(n) / ϵ ^(n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1+ϵ)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2^O(n)).
READ FULL TEXT