A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents

Combinatorica - Tập 20 - Trang 545-568 - 2000
Nathan Linial1, Alex Samorodnitsky2, Avi Wigderson3
1School of Computer Science and Engeneering, The Hebrew University; Jerusalem 91904, Israel; E-mail: [email protected], , IL
2School of Mathematics, Institute for Advanced Study; Princeton, NJ 08540, U.S.A.; E-mail: [email protected], , US
3School of Mathematics, Institute for Advanced Study; Princeton, NJ 08540, U.S.A.; and School of Computer Science and Engineering; The Hebrew University; Jerusalem, 91904, Israel; E-mail: [email protected], , US

Tóm tắt

matrix to within a multiplicative factor of . 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 decision algorithm for bipartite perfect matching, conceptually different from classical approaches.

Thông tin
Thông tin xuất bản

Combinatorica

Tập 20

545-568

Thông tin tác giả