Matrix scaling by network flow

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

17 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Pages848-854
Number of pages7
DOIs
Publication statusPublished - 2007

Publication series

NameSODA
Volume07

Keywords

  • Algorithms
  • Matrix scaling problem
  • scaling algorithm

Fingerprint

Dive into the research topics of 'Matrix scaling by network flow'. Together they form a unique fingerprint.

Cite this