TY - JOUR
T1 - On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms
AU - Kalantari, Bahman
AU - Khachiyan, Leonid
N1 - Funding Information:
Correspondence to: Prof. B. Kalantari, Department of Computer Science, Rutgers University, New Brunswick, NJ 08903, USA. * This research was supported in part by the National Science Foundation under Grant No. CCR-9208371.
PY - 1993/12
Y1 - 1993/12
N2 - We consider the well-known RAS algorithm for the problem of positive matrix scaling. We 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, our bound implies that for any dimension d the method is a fully polynomial-time approximation scheme. We also present a randomized variant of the algorithm whose (expected) running time improves that of the deterministic method by a factor of d.
AB - We consider the well-known RAS algorithm for the problem of positive matrix scaling. We 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, our bound implies that for any dimension d the method is a fully polynomial-time approximation scheme. We also present a randomized variant of the algorithm whose (expected) running time improves that of the deterministic method by a factor of d.
KW - RAS method
KW - diagonal matrix scaling
KW - fully polynomial-time approximation schemes
KW - randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=38249001115&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249001115&partnerID=8YFLogxK
U2 - 10.1016/0167-6377(93)90087-W
DO - 10.1016/0167-6377(93)90087-W
M3 - Article
AN - SCOPUS:38249001115
SN - 0167-6377
VL - 14
SP - 237
EP - 244
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -