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

balanced partitiondiscrepancynormvector 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.

Review text

Let \(d,r\in {\mathbb N}\) and \(\| {\cdot}\| \) be any norm on~\({\mathbb R}^d\). Let \(B\) denote the unit ball with respect to this norm. It is shown that any sequence \(v_1,v_2,\dots\) of vectors in~\(B\) can be partitioned into \(r\) subsequences \(V_1,\dots, V_r\) in a balanced manner with respect to the partial sums: For all \(n\in {\mathbb N}\), \(\ell\leqslant r\), we have \(\| \sum_{i\leqslant k,\;v_i\in V_\ell} v_i-\frac 1r\sum _{i\leqslant k} v_i\| \leqslant 2.005d\). A~similar bound holds for partitioning sequences of vector sets. Both result extend an earlier one of \textit{I. Bárány} and \textit{V. S. Grinberg} [Linear Algebra Appl. 41, 1--9 (1981; Zbl 0467.90079)] to partitions in arbitrary many classes. It is worth mentioning that the results hold for all norms in~\({\mathbb R}^d\).

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

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

Cited in

(8)

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

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)