Symmetry-dependence in Rounding of a Convex Body

The symmetry measure of a convex body $S\subset {\mathbb{R}}^n$ is given by $$\mathrm{sym}(S):=\max \{\alpha \ge 0:\text{ there exists }x\in S\text{ such that }-\alpha (S-x)\subseteq S-x\},$$ where such an $x$ is called a Minkowski center. We prove that every convex body $S$ admits a $\sqrt{\frac{n}{\mathrm{sym}(S)}}$-rounding of $S$, namely, there exists an origin-centered ellipsoid $E$ and a center $c$ such that the following rounding holds: $$E\subseteq S-c\subseteq \sqrt{\frac{n}{\mathrm{sym}(S)}}E\mathrm{.}$$ This result was conjectured in 2005 by Belloni and Freund. As special cases, this recovers the known result of an $n$-rounding of $S$ (since it always holds that $\mathrm{sym}(S)\ge 1\mathrm{/}n$), and also recovers the known result of a $\sqrt{n}$-rounding when $\mathrm{sym}(S)=1$. In the case when $S$ is a polytope given as the convex hull of points, the desired rounding is produced by a regularized minimum volume covering ellipsoid problem where the regularization is with respect to the Minkowski center. Similarly, when $S$ is a polytope given as the intersection of halfspaces, such a rounding is produced by a regularized maximum volume inscribed ellipsoid problem. We also show that the factor $\sqrt{\frac{n}{\mathrm{sym}(S)}}$ is nearly tight in its dependence on dimension and symmetry. When $\frac{n+1}{1+\mathrm{sym}(S)}$ is an integer, we show by explicit construction that the factor $\sqrt{\frac{n}{\mathrm{sym}(S)}}$ is tight. In the more general case, for every dimension $n$ and every admissible symmetry value, we construct a polytope $S$ for which every rounding is at least $\sqrt{\frac{2}{3}}\sqrt{\frac{n}{\mathrm{sym}(S)}}$.