= Matrix rounding with fixed margins
{title2=$b_{ij}\in\{\lfloor a_{ij}\rfloor,\lceil a_{ij}\rceil\}$}
A <matrix> of nonnegative <rational numbers> with <integer> row and column <sums> can be rounded entrywise up or down while preserving all those <sums>. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its <floor> and <fractional part>. The residual row and column <sums> $r_i=\sum_jf_{ij}$ and $c_j=\sum_if_{ij}$ are <nonnegative integers>. Build a <flow network> with source-to-row <flow network edge capacities> $r_i$, row-to-column <flow network edge capacities> one where $f_{ij}>0$, and column-to-sink <flow network edge capacities> $c_j$. The <fractional parts> supply a <feasible flow> saturating all source arcs. The <integral max-flow theorem> supplies an integral one of the same total value. If its middle-arc <flows> are $h_{ij}\in\{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required <matrix>. This is a constructive <polynomial-time algorithm>; no multiplication by a common denominator is required.
Back to article page
