The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \[
\mathrm{sym}(S):=\max\{\alpha\ge0:\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\,.
\]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/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. In both of these cases, the rounding can be computed by first solving a linear optimization problem (to compute \(\mathrm{sym}(S)\) and a Minkowski center), and then solving a convex optimization problem with a logarithmic determinant objective, second-order cone constraints, and one semidefinite cone constraint.
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)}}\).