On the complexity of nonnegative-matrix scaling

DOI10.1016/0024-3795(94)00188-XzbMath0849.15003OpenAlexW2034025033MaRDI QIDQ1915608

Bahman Kalantari, Leonid G. Khachiyan

Publication date: 30 June 1996

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

Full work available at URL: https://doi.org/10.1016/0024-3795(94)00188-x

zbMATH Keywords

normsstochastic matrixcomplexity boundscaling factorsnonnegative double

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Complexity and performance of numerical algorithms (65Y20) Stochastic matrices (15B51) Conditioning of matrices (15A12)

Related Items

A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices, Unnamed Item, A fast projected fixed-point algorithm for large graph matching, An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs, Apportionment with parity constraints, On testing Hamiltonicity of graphs, On complexity of matrix scaling, Scientific contributions of Leo Khachiyan (a short overview), On the complexity of general matrix scaling and entropy minimization via the RAS algorithm, On the diagonal scaling of Euclidean distance matrices to doubly stochastic matrices, An approximation algorithm for counting contingency tables, Enumerating Contingency Tables via Random Permanents, Scaling of symmetric matrices by positive diagonal congruence, Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling, Scaling matrices and counting the perfect matchings in graphs, Matrix scaling and explicit doubly stochastic limits, A hierarchically low-rank optimal transport dissimilarity measure for structured data

Cites Work

• Matrix scaling, entropy minimization, and conjugate duality. I: Existence conditions
• 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
• A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices
• Concerning nonnegative matrices and doubly stochastic matrices
• Scaling of matrices to achieve specified row and column sums
• On matrices with doubly stochastic pattern
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• Extensions of Jentzsch's Theorem
• A Comparative Study of Algorithms for Matrix Balancing
• A new approach to the maximum-flow problem
• Diagonal Matrix Scaling and Linear Programming
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Reduction of a Matrix with Positive Elements to a Doubly Stochastic Matrix
• Convex Sets of Non-Negative Matrices
• The Distribution of Positive Elements in Doubly-Stochastic Matrices
• Note on Nonnegative Matrices
• Unnamed Item
• Unnamed Item