Balanced Partitions of Vector Sequences
| dc.creator | Bárány, Imre | |
| dc.creator | Doerr, Benjamin | |
| dc.date | 2004-05-17 | |
| dc.date.accessioned | 2026-07-07T05:08:21Z | |
| dc.date.available | 2026-07-07T05:08:21Z | |
| dc.description | Let $d, r \in \N$, $\|\cdot\|$ any norm on $\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 \N$, $\ell \le r$, we have $\|\sum_{i \le k, v_i \in V_\ell} v_i - \tfrac 1r \sum_{i \le k} v_i\| \le 2.0005 d$. 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. | |
| dc.description | 8 pages | |
| dc.identifier | https://arxiv.org/abs/math/0405335 | |
| dc.identifier | http://arxiv.org/abs/math/0405335 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71225 | |
| dc.subject | Combinatorics | |
| dc.subject | 11K38; 05A18 | |
| dc.title | Balanced Partitions of Vector Sequences | |
| dc.type | text |