Diagonal matrix scaling is NP-hard

DOI10.1016/0024-3795(94)00099-9zbMATH Open0840.65030OpenAlexW1995361925MaRDI QIDQ1908195FDOQ1908195

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Concerning nonnegative matrices and doubly stochastic matrices
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• Diagonal Matrix Scaling and Linear Programming
• On matrices with doubly stochastic pattern
• Note on Nonnegative Matrices

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)

Recommendations

• Title not available (Why is that?) 👍 👎
• On the complexity of nonnegative-matrix scaling 👍 👎
• Diagonal Matrix Scaling and Linear Programming 👍 👎
• On complexity of matrix scaling 👍 👎
• Semidefinite programming and matrix scaling over the semidefinite cone. 👍 👎

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)