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=(aij)
is to be scaled, by
multiplying its rows and columns by unknown positive multipliers λi
and
μj, such that the resulting matrix (aijλiμj)
has specified row and
column sums ri and sj. We give an
algorithm that achieves the
desired row and column sums with a maximum absolute error ε
in
O(n4(logn+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.