2-WAY ROUNDING

Given n real numbers 0 less than or equal to x(1),...,x(n) < 1 and a p ermutation sigma of {1,...,n}, we can always find ($) over bar x(1),.. .,($) over bar x(n) is an element of {0,1} so that the partial sums ($ ) over bar x(1) +...+ ($) over bar x(k) and ($) over bar x(sigma 1) +. ..+ x(sigma k) by at most n/(n+1), for 1 less than or equal to k less than or equal to 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.