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

Bahman Kalantari; Leonid Khachiyan

doi:10.1016/0167-6377(93)90087-W

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

Bahman Kalantari
, Leonid Khachiyan

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

20 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 language	English (US)
Pages (from-to)	237-244
Number of pages	8
Journal	Operations Research Letters
Volume	14
Issue number	5
DOIs	https://doi.org/10.1016/0167-6377(93)90087-W
State	Published - 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

Access to Document

10.1016/0167-6377(93)90087-W

Cite this

@article{bbdf393a77434d4fb94eb410adddfc50,

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.",

keywords = "RAS method, diagonal matrix scaling, fully polynomial-time approximation schemes, randomized algorithms",

author = "Bahman Kalantari and Leonid Khachiyan",

note = "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.",

year = "1993",

month = dec,

doi = "10.1016/0167-6377(93)90087-W",

language = "English (US)",

volume = "14",

pages = "237--244",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

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 - https://www.scopus.com/pages/publications/38249001115

UR - https://www.scopus.com/pages/publications/38249001115#tab=citedBy

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 -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this