On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms

The authors consider the well-known RAS algorithm for the problem of positive matrix scaling. They give a new bound on the number of iterations of the method for scaling a given d-dimensional matrix A to a prescribed accuracy. Although the RAS method is not a polynomial-time algorithm even for d=2, the present bound implies that for any dimension d the method is a fully polynomial-time approximation scheme. The authors also present a randomized variant of the algorithm whose (expected) running time improves that of the deterministic method by a factor of d.