Two-way rounding

Abstract

Given $n$ real numbers $0\le x_1,...,x_n<1$ and a permutation~$\sigma$ of $\{1,...,n\}$, we can always find $\xbar_1,...,\xbar_n\in\{0,1\}$ so that the partial sums $\xbar_1+... +\xbar_k$ and $\xbar_{σ1}+... +\xbar_{σk}$ differ from the unrounded values $x_1+...+x_k$ and $x_{\sigma 1}+...+x_{\sigma k}$ by at most $n/(n+1)$, for $1\le k\le n$. The latter bound is best possible. The proof uses an elementary argument about flows in a certain network, and leads to a simple algorithm that finds an optimum way to round.