Balanced Partitions of Vector Sequences

Abstract

Let $d,r\in \mathbb{N}$, $\Vert \cdot \Vert$ any norm on ${\mathbb{R}}^d$ and $B$ denote the unit ball with respect to this norm. We show that any sequence $v_1,v_2,...$ of vectors in $B$ can be partitioned into $r$ subsequences $V_1,...,V_r$ in a balanced manner with respect to the partial sums: For all $n\in \mathbb{N}$, $\ell \le r$, we have $\Vert {\sum }_{i\le k,v_i\in V_{\ell }}{v}_i-\frac{1}{r}{\sum }_{i\le k}{v}_i\Vert \le 2.0005d$. A similar bound holds for partitioning sequences of vector sets. Both results extend an earlier one of Bárány and Grinberg (1981) to partitions in arbitrarily many classes.

8 pages