On complexity of matrix scaling
type: Item
instance of: scholarly article
title: On complexity of matrix scaling
zbMATH Open document ID: 0952.15005
DOI: 10.1016/S0024-3795(99)00212-8
author: Uriel G. Rothblum
author: Arkadi Nemirovski
published in: Linear Algebra and its Applications
publication date: 2001-01-03T00:00:00Z
review text: The line sum scaling (LSS) problem for a nonnegative matrix \(A\) is to find positive definite diagonal matrices \(Y\), \(Z\) which result in prescribed row and column sums of the scaled matrix \(YAZ\). The problem (LSS) can be reformulated as a specific geometric programming problem (GS). The authors prove that \(\epsilon \)-versions of the problem (GS) can be solved in time polynomial and they apply these results to the (LSS) problem. They conclude applying their results on polynomial time solvability of (GS) to the balancing problem for a nonnegative matrix [cf. \textit{B. Kalantari, L. Khachiyan} and \textit{A. Shokoufondah}, SIAM J. Matrix Anal. Appl. 18, No. 2, 450-463 (1997; Zbl 0882.65031)] and to a multi-index sum scaling problem.
reviewed by: M. Ladra
Mathematics Subject Classification ID: 15A12
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1419880
zbMATH Keywords: matrix scaling
zbMATH Keywords: matrix balancing
zbMATH Keywords: polynomial-time complexity
zbMATH Keywords: line sum scaling
zbMATH Keywords: nonnegative matrix
zbMATH Keywords: geometric programming
MaRDI profile type: Publication
cites work: Q4135211
cites work: On the complexity of nonnegative-matrix scaling
cites work: On the Complexity of Matrix Balancing
cites work: Q3050157
cites work: Q4542587
cites work: Q4717955
cites work: Scalings of matrices which have prespecified row sums and column sums via optimization
cites work: Generalized scalings satisfying linear equations
full work available at URL: s0024-3795(99)00212-8
OpenAlex ID: W2022242474
description: scientific article; zbMATH DE number 1419880