Balanced Partitions of Vector Sequences

Details Balanced Partitions of Vector Sequences Balanced Partitions of Vector Sequences

2004-05-17

arxiv.org/abs/math/0405335v1

Mathematics

Combinatorics

8 pages

Scientific paper

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\'ar\'any and Grinberg (1981) to partitions in arbitrarily many classes.

Affiliated with

Also associated with

No associations

Rating

Balanced Partitions of Vector Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Balanced Partitions of Vector Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balanced Partitions of Vector Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-366450