Algorithmic Aspects of Matrix Scaling and Related Problems

点击翻译按钮获取中文摘要

This project will investigate the algorithmic aspects of matrix scaling problems. These problems call for pre and post multiplication of a given matrix by two diagonal matrices so that the resulting scaled matrix satisfies prescribed conditions. A wide variety of practical and theoretical problems fall within the general framework of matrix scaling problems. These include: (i) scaling of nonnegative matrices to prescribed row-column sums, (ii) similarity scaling, balancing, and matrix preconditioning, (iii) scaling of nonnegative matrices to prescribed row-column maxima-minima, (iv) scaling of positive semidefinite matrices, and some others. Cases (i) and (ii) of the scaling problem and their applications have been studied for a long time, case (iii) of the problem includes the problem of determining the ergodic values of matrix games, and case (iv) turn out to be a natrual generalization of linear programming. The emphasis of this research is the study of the computational complexity of various types of scaling problems, as well as the development of effective algorithms and approximation schemes, and to test the algorithms computationally.