Balanced partitions of vector sequences

DOI10.1016/J.LAA.2005.10.024zbMATH Open1091.15030arXivmath/0405335OpenAlexW2165423230MaRDI QIDQ2369044FDOQ2369044

Authors: Benjamin Doerr, Imre Bárány 

Publication date: 28 April 2006

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Balancing vectors in the max norm
• On some combinatorial questions in finite-dimensional spaces
• Multicolour Discrepancies

Cited In (7)

• 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 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)