Balanced partitions of vector sequences

Bárány, Imre; Doerr, Benjamin

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Balanced partitions of vector sequences

MPS-Authors

/persons/resource/persons44338

Doerr, Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Bárány, I., & Doerr, B. (2006). Balanced partitions of vector sequences. Linear Algebra and its Applications, 414, 464-469.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-223D-3

Abstract

Let and · be any norm on . 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 , we have . A similar bound holds for partitioning sequences of vector sets. Both results extend an earlier one of Bárány and Grinberg [I. Bárány, V.S. Grinberg, On some combinatorial questions in finite-dimensional spaces, Linear Algebra Appl. 41 (1981) 1–9] to partitions in arbitrarily many classes.