### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 237-244 |

Number of pages | 8 |

Journal | Operations Research Letters |

Volume | 14 |

Issue number | 5 |

DOIs | |

State | Published - Jan 1 1993 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics

### Keywords

- RAS method
- diagonal matrix scaling
- fully polynomial-time approximation schemes
- randomized algorithms

### Cite this

*Operations Research Letters*,

*14*(5), 237-244. https://doi.org/10.1016/0167-6377(93)90087-W

}

*Operations Research Letters*, vol. 14, no. 5, pp. 237-244. https://doi.org/10.1016/0167-6377(93)90087-W

**On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms.** / Kalantari, Bahman; Khachiyan, Leonid.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Kalantari, Bahman

AU - Khachiyan, Leonid

PY - 1993/1/1

Y1 - 1993/1/1

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

VL - 14

SP - 237

EP - 244

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -