Forgot your password?
Economical Convex Coverings and Applications
Wednesday, December 14th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)
David Mount, Dept. of Computer Science and Institute for Advanced Computer Studies, University of Maryland
Abstract:
Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Given a convex body K and epsilon > 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 epsilon expansion of K.
It is known how to construct coverings of size n^{O(n)}/epsilon^{(n-1)/2} for general convex bodies in R^n. In special cases, such as when the convex body is the Lp unit ball, this bound has been improved to 2^{O(n)}/epsilon^{(n-1)/2}. In this talk, I will present results of an upcoming paper in SODA 2023, where we show that such an improvement holds for arbitrary convex bodies.
I will also discuss applications of these results to other problems in convex approximation, including convex approximations in the Banach-Mazur metric, and approximation algorithms for the closest-vector problem and integer programming.
(This work will be presented at SODA 2023. Joint work with Sunil Arya and Guilherme da Fonseca.)
