Balanced partitions of vector sequences

DOI10.1016/J.LAA.2005.10.024MaRDI QIDQ2369044zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Imre Bárány

Publication date 28 April 2006

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0405335

zbMATH Keywords

normdiscrepancybalanced partitionvector balancing game

Mathematics Subject Classification ID

Partitions of sets (05A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Programming in abstract spaces (90C48)

Abstract: Let $d,rinN$, $|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,\mathrm{...}$ of vectors in $B$ can be partitioned into $r$ subsequences $V_1,\mathrm{...},V_r$ in a balanced manner with respect to the partial sums: For all $ninN$, $elller$, we have $|su{m}_{ilek,v_{i}in{V}_{e}ll}{v}_i-frac1rsu{m}_{ilek}{v}_i|le2.0005d$. 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.

Recommendations

• Balancing sums of random vectors
• Balancing vectors in the max norm
• A balancing strategy
• On series of signed vectors and their rearrangements
• Small subset sums

Cites work

• scientific article; zbMATH DE number 863495 (Why is no real title available?)
• Balancing vectors in the max norm
• Multicolour Discrepancies
• On some combinatorial questions in finite-dimensional spaces

Cited in

(8)

• Packing spanning graphs from separable families
• Balancing vectors in the max norm
• Balancing Gaussian vectors
• Balanced configurations of \(2 n + 1\) plane vectors
• On series of signed vectors and their rearrangements
• Balancing unit vectors
• Balancing sums of random vectors
• Block partitions of sequences

This page was built for publication: Balanced partitions of vector sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369044)