04-19   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Imre Bárány, Benjamin Doerr:

Balanced Partitions of Vector Sequences

Let d, r ∈ N and ¦¦ · ¦¦ be any norm on Rd . Let B denote the unit ball with respect to this norm. We show that any sequence v1,v2, ... of vectors in B can be partitioned into r subsequences V1, ... , Vr in a balanced manner with respect to the partial sums:

For all n ∈ N, l ≤ r, we have ¦¦ ∑i ≤ k, vi ∈ Vl vi - (1/r) ∑i ≤ k vi ¦¦ ≤ 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.

Mathematics Subject Classification (1991): 11K38

Keywords: Discrepancy, partition, linear algebra

Mail an Jens Burmeister
[Thu Feb 19 18:56:36 2009]
Impressum