Abstract
A given nonnegative n x 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(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.
We give an algorithm that achieves the desired row and column sums with a maximum absolute error ε in O(n4(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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms |
| Place of Publication | United States |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 848-854 |
| Number of pages | 7 |
| DOIs | |
| Publication status | Published - 2007 |
Publication series
| Name | SODA |
|---|---|
| Volume | 07 |
Keywords
- Algorithms
- Matrix scaling problem
- scaling algorithm