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

Bahman Kalantari, Leonid Khachiyan

Research output: Contribution to journalArticle

11 Citations (Scopus)

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 - Jan 1 1993

Fingerprint

Rate of Convergence
Scaling
Polynomials
Fully Polynomial Time Approximation Scheme
Positive Matrices
Polynomial-time Algorithm
Iteration
Imply
Rate of convergence

All Science Journal Classification (ASJC) codes

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

Cite this

@article{e2b4ecb476c2482799e58e909ed9d478,
title = "On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms",
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.",
author = "Bahman Kalantari and Leonid Khachiyan",
year = "1993",
month = "1",
day = "1",
doi = "https://doi.org/10.1016/0167-6377(93)90087-W",
language = "English (US)",
volume = "14",
pages = "237--244",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "5",

}

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

In: Operations Research Letters, Vol. 14, No. 5, 01.01.1993, p. 237-244.

Research output: Contribution to journalArticle

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.

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 - https://doi.org/10.1016/0167-6377(93)90087-W

DO - https://doi.org/10.1016/0167-6377(93)90087-W

M3 - Article

VL - 14

SP - 237

EP - 244

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -