Balanced partitions of vector sequences

Bárány, Imre; Doerr, Benjamin

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

学術論文

Balanced partitions of vector sequences

MPS-Authors

/persons/resource/persons44338

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

External Resource

There are no locators available

Fulltext (restricted access)

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

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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

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

要旨

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.