Return to Question

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 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$.

Thanks.

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$.

Thanks.

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 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 for geometric coverage problems. 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$.

Thanks.

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 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$.

Thanks.