We are interested in the following

Lemma. Let $V\subset [0,1]^n\subset\mathbb R^n$ be a set of $n$-dimensional vectors. Then for each $r\le |V|$ there exists a partition $$V=V_1\cup V_2\cup\dots \cup V_r$$ such that for each $i\le r$ holds

$$\left\|\frac 1r\sum_{v\in V} v -\sum_{v\in V_i} v\right\|\le 2n.$$

Here $\|\cdot\|$ is $\ell^\infty$ norm, that is if $x=(x_1,x_2,\dots, x_n)$ then $\|x\|=\max |x_i|$.

Lemma should be a corollary of Theorem 3 from a paper "Balanced partitions of vector sequences" by Imre Bárany and Benjamin Doerr. But we have some specific requirements. We apply Lemma for approximative algorithms in graph theory. So we need more simple and clear proof, maybe that allowing to find a required partition in polynomial (or even linear) time. I may try to devise such a proof (it seems that a greedy algorithm has complexity $O(|V|^2)$ and yields a similar upper bound), but I hope that it is already known, because in the paper is considered more complex problem than Lemma. Also maybe the upper bound differs from $2n$ and there is $\sqrt{n}$ instead of $n$ or an other constant instead of $2$.



Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.