## Günter Rote and Martin Zachariasen:

# Matrix scaling by network flow

*In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), New Orleans, January 2007, pp. 848-854.
*
### Abstract

A given nonnegative *n*×*n* matrix *A*=(*a*_{ij})
is to be scaled, by
multiplying its rows and columns by unknown positive multipliers λ_{i}
and
μ_{j}, such that the resulting matrix (*a*_{ij}λ_{i}μ_{j})
has specified row and
column sums *r*_{i} and *s*_{j}. We give an
algorithm that achieves the
desired row and column sums with a maximum absolute error ε
in
*O*(*n*^{4}(log*n*+log(*h*/ε)))
steps,
where *h* is the overall total of the
result matrix. Our algorithm is a scaling algorithm. It solves a
sequence of
more and more refined discretizations. The discretizations are
minimum-cost
network flow problems with convex piecewise linear costs. These
discretizations
are interesting in their own right because they arise in proportional
elections.
Last update: January 12, 2007.