Diagonal matrix scaling is NP-hard

DOI10.1016/0024-3795(94)00099-9MaRDI QIDQ1908195zbMATH OpenOpenAlexFDO

Authors 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

NP-hardsymmetric matrixlogarithmic barrier functiondiagonal matrix scaling

Mathematics Subject Classification ID

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

Recommendations

• Diagonal Matrix Scaling and Linear Programming
• On the complexity of nonnegative-matrix scaling
• On complexity of matrix scaling
• Semidefinite programming and matrix scaling over the semidefinite cone.
• scientific article; zbMATH DE number 733109

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 4197755 (Why is no real title available?)
• Concerning nonnegative matrices and doubly stochastic matrices
• Diagonal Matrix Scaling and Linear Programming
• Note on Nonnegative Matrices
• On matrices with doubly stochastic pattern
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix

Cited in

(6)

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

This page was built for publication: Diagonal matrix scaling is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908195)