The Vector Balancing Constant for Zonotopes

MaRDI QIDQ6415463zbMATH OpenFDO

Authors Laurel Heck, Victor Reis, Thomas Rothvoß

Publication date 28 October 2022

Abstract: The vector balancing constant $mathrmvb(K,Q)$ of two symmetric convex bodies $K,Q$ is the minimum $rgeq0$ so that any number of vectors from $K$ can be balanced into an $r$-scaling of $Q$. A question raised by Schechtman is whether for any zonotope $Ksubseteqmathbb{R}^d$ one has $mathrmvb(K,K)lesssimsqrtd$. Intuitively, this asks whether a natural geometric generalization of Spencer's Theorem (for which $K=B_i^{d}nfty$) holds. We prove that for any zonotope $Ksubseteqmathbb{R}^d$ one has $mathrmvb(K,K)lesssimsqrtdlogloglogd$. Our main technical contribution is a tight lower bound on the Gaussian measure of any section of a normalized zonotope, generalizing Vaaler's Theorem for cubes. We also prove that for two different normalized zonotopes $K$ and $Q$ one has $mathrmvb(K,Q)lesssimsqrtdlogd$. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.

This page was built for publication: The Vector Balancing Constant for Zonotopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415463)