= Solution
Separate the forced <integer> portion from the choice of rounding direction. Put $p_{ij}=\lfloor a_{ij}\rfloor$ and $q_{ij}=a_{ij}-p_{ij}$. Define residual demands
$$
r_i=\sum_jq_{ij}=\sum_ja_{ij}-\sum_jp_{ij},\qquad c_j=\sum_iq_{ij}=\sum_ia_{ij}-\sum_ip_{ij}.
$$
These are <nonnegative integers>, since the original row and column <sums> are <integers>. Also $\sum_ir_i=\sum_jc_j=:T$. Each <fractional part> satisfies $0\leq q_{ij}<1$.
Construct a <flow network> with a <vertex> for each row and column, source-to-row arcs of <flow network edge capacity> $r_i$, row-to-column arcs of <flow network edge capacity> one exactly where $q_{ij}>0$, and column-to-sink arcs of <flow network edge capacity> $c_j$. The amounts $q_{ij}$ themselves define a fractional <feasible flow> of <flow value> $T$. No <flow> can exceed $T$, the total source <flow network edge capacity>. Because all constructed <flow network edge capacities> are <integers>, an integral <maximum flow> also has <flow value> $T$ and saturates every source and sink arc.
Let $h_{ij}$ be its middle-arc <flow>, taking $h_{ij}=0$ when that arc is absent. Then $h_{ij}\in\{0,1\}$, and the required answer is
$$
\boxed{b_{ij}=\lfloor a_{ij}\rfloor+h_{ij}.}
$$
At an already integral entry no middle arc exists, so that entry stays fixed. At a nonintegral entry the two possibilities are precisely its <floor> and <ceiling>. <Flow conservation> gives $\sum_jh_{ij}=r_i$ and $\sum_ih_{ij}=c_j$, preserving every original row and column <sum>.
This is <matrix rounding with fixed margins>. There are $m+n+2$ <vertices> and at most $mn+m+n$ arcs. Exact <rational arithmetic> computes the <floors> and residual demands in <polynomial time> in the encoded input length; the resulting <flow network edge capacities> are small <integers>, so there is no need to scale by a potentially large common denominator.
Back to article page
