On complexity of matrix scaling (Q1970454)

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.