A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents

Authors
Linial, N Samorodnitsky, A Wigderson, A
Citation
N. Linial et al., A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, COMBINATORI, 20(4), 2000, pp. 545-568
Citations number
31
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
20
Issue
4
Year of publication
2000
Pages
545 - 568
Database
ISI
SICI code
0209-9683(2000)20:4<545:ADSPAF>2.0.ZU;2-R
Abstract
We present a deterministic strongly polynomial algorithm that computes the permanent of a, nonnegative nxn matrix to within a multiplicative factor of e(n). To this end we develop the first strongly polynomial-time algorithm for matrix scaling - an important nonlinear optimization problem with many applications. Our work suggests a simple new (slow) polynomial time decisio n algorithm for bipartite perfect matching, conceptually different from cla ssical approaches.