On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms

DOI10.1016/0167-6377(93)90087-WzbMath0795.65022MaRDI QIDQ1318656

Bahman Kalantari, Leonid G. Khachiyan

Publication date: 6 April 1994

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

convergencepolynomial-time approximation schemenumber of iterationsRAS matrix scaling algorithms

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Conditioning of matrices (15A12)

Related Items

A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices, On the complexity of nonnegative-matrix scaling, Unnamed Item, Scientific contributions of Leo Khachiyan (a short overview), On the complexity of general matrix scaling and entropy minimization via the RAS algorithm, Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling, Matrix scaling and explicit doubly stochastic limits, On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms

Cites Work

• Unnamed Item
• An extension of a theorem of Darroch and Ratcliff in loglinear models and its application to scaling multidimensional matrices
• On the scaling of multidimensional matrices
• Scalings of matrices which have prespecified row sums and column sums via optimization
• On the RAS-algorithm
• On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• Extensions of Jentzsch's Theorem
• A Comparative Study of Algorithms for Matrix Balancing
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices