Nearly-Tight Bounds for Zonotope Containment and Beyond

Abstract

We investigate the convex-body containment problem $\max \{s>0:sZ\subseteq Q\}$, where the outer body $Q\subseteq {\mathbb{R}}^d$ is described by a membership oracle and the inner body $Z\subseteq {\mathbb{R}}^d$ is a zonotope. Our main result is a sampling-based $O(\sqrt{d})$-approximation algorithm for this problem that almost matches the lower bound of $\Omega (\sqrt{d/\log d})$ by Khot and Naor in the oracle model. Assuming zonotopes can be sparsified by a linear number of generators, which is referred to as Talagrand conjecture, our approach attains the optimal approximation factor of $\Theta (\sqrt{d/\log d})$. Our second main result is a proof of Talagrand's conjecture for $\Delta$-modular zonotopes whenever $\Delta$ is constant. Those zonotopes are of the form $Z=\{Wx:\Vert x{\Vert }_{\infty }\le 1\}$ where the non-zero $d\times d$ sub-determinants of $W$ are between $1$ and $\Delta$. This result establishes a connection between zonoid sparsification and spectral sparsification of Batson, Spielman and Srivastava. We complement these results with a universal $\Omega (\sqrt{d/\log d})$ lower bound holding for all zonotopes. Finally, we consider containment problems $\max \{s>0:sK\subseteq Q\}$, for general convex bodies $K\subseteq {\mathbb{R}}^d$. A result of Naszódi on approximating $K\subseteq {\mathbb{R}}^d$ by a polytope implies a $\Theta (d/\log d)$ approximation algorithm in polynomial time. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal $O(\sqrt{d})$-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.