Two-Way Rounding
Donald E. Knuth · SIAM Journal on Discrete Mathematics · 1995
Given n real numbers $0 \leq x_1 , \ldots , x_n < 1$ and a permutation $\sigma $ of $\{ 1, \ldots ,n \}$, we can always find $\bar x_1 , \cdots ,\bar x_n \in \{ 0,1 \}$ so that the partial sums $\bar x_1 + \cdots + \bar x_k $ and $\bar x_{\sigma 1} + \cdots + \bar x_{\sigma k} $ differ from the unrounded values $x_1 + \cdots + x_k $ and $x_{\sigma 1} + \cdots + x_{\sigma k} $ by at most $n/(n + 1)$, for $1 \leq k \leq 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.