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

Bahman Kalantari, Leonid Khachiyan

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

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 languageEnglish (US)
Pages (from-to)237-244
Number of pages8
JournalOperations Research Letters
Volume14
Issue number5
DOIs
StatePublished - Dec 1993

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

Fingerprint

Dive into the research topics of 'On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms'. Together they form a unique fingerprint.

Cite this