Colorful Vector Balancing

Abstract

We extend classical estimates for the vector balancing constant of ${\mathbb{R}}^d$ equipped with the Euclidean and the maximum norms proved in the 1980's by showing that for $p=2$ and $p=\infty$, given vector families $V_1,\dots ,V_n\subset B_p^d$ with $0\in {\sum }_{i=1}^n\mathrm{conv}{V}_i$, one may select vectors $v_i\in V_i$ with $\Vert v_1+\dots +v_n{\Vert }_2\le \sqrt{d}$ for $p=2$, and $\Vert v_1+\dots +v_n{\Vert }_{\infty }\le O(\sqrt{d})$ for $p=\infty$. These bounds are sharp and asymptotically sharp, respectively, for $n\ge d$. The proofs combine linear algebraic and probabilistic methods with a Gaussian random walk argument.

20 pages, 1 figure. Final version, to appear in Mathematika