On complexity of matrix scaling

DOI10.1016/S0024-3795(99)00212-8zbMath0952.15005OpenAlexW2022242474MaRDI QIDQ1970454

Uriel G. Rothblum, Arkadi Nemirovski

Publication date: 3 January 2001

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0024-3795(99)00212-8

zbMATH Keywords

nonnegative matrixgeometric programmingpolynomial-time complexitymatrix scalingmatrix balancingline sum scaling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Conditioning of matrices (15A12)

Related Items

Convex Relaxations for Permutation Problems, Unnamed Item, A fast projected fixed-point algorithm for large graph matching, Apportionment with parity constraints, Near-linear convergence of the random Osborne algorithm for matrix balancing, On the complexity of general matrix scaling and entropy minimization via the RAS algorithm, Enumerating Contingency Tables via Random Permanents, Scaling of symmetric matrices by positive diagonal congruence, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor, Spectral Analysis of Matrix Scaling and Operator Scaling, A hierarchically low-rank optimal transport dissimilarity measure for structured data

Cites Work

• Scalings of matrices which have prespecified row sums and column sums via optimization
• Generalized scalings satisfying linear equations
• On the complexity of nonnegative-matrix scaling
• On the Complexity of Matrix Balancing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item