Diagonal matrix scaling is NP-hard

DOI10.1016/0024-3795(94)00099-9zbMath0840.65030OpenAlexW1995361925MaRDI QIDQ1908195

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)00099-9

zbMATH Keywords

logarithmic barrier functionNP-hardsymmetric matrixdiagonal matrix scaling

Mathematics Subject Classification ID

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

Related Items

Tensors in computations, A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices, A tutorial on the balanced minimum evolution problem, An information theory perspective on the balanced minimum evolution problem, Scientific contributions of Leo Khachiyan (a short overview)

Cites Work

• Unnamed Item
• Unnamed Item
• Concerning nonnegative matrices and doubly stochastic matrices
• On matrices with doubly stochastic pattern
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• Diagonal Matrix Scaling and Linear Programming
• Note on Nonnegative Matrices