Random Walks on Weighted Graphs and Applications to on-line Algorithms

Don Coppersmith; Peter Doyle; Prabhakar Raghavan; Marc Snir

doi:10.1145/174130.174131

Random Walks on Weighted Graphs and Applications to on-line Algorithms

Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir

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

Abstract

The design and analysis of randomized on-line algorithms are studied. This problem is shown to be closely related to the synthesis of random wdlks on graphs with positive real costs on their edges. A theory is developed for the synthesis of such wdlks, and it is employed to design competitive on-line algorithms.

Original language	English (US)
Pages (from-to)	421-453
Number of pages	33
Journal	Journal of the ACM (JACM)
Volume	40
Issue number	3
DOIs	https://doi.org/10.1145/174130.174131
State	Published - Jan 7 1993
Externally published	Yes

Keywords

metrical tasks
server problem

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Online availability

10.1145/174130.174131

Library availability

Discover UIUC Full Text

Cite this

@article{8935efb9ec8a4d84b9eddc8c7fe0b630,

title = "Random Walks on Weighted Graphs and Applications to on-line Algorithms",

abstract = "The design and analysis of randomized on-line algorithms are studied. This problem is shown to be closely related to the synthesis of random wdlks on graphs with positive real costs on their edges. A theory is developed for the synthesis of such wdlks, and it is employed to design competitive on-line algorithms.",

keywords = "metrical tasks, server problem",

author = "Don Coppersmith and Peter Doyle and Prabhakar Raghavan and Marc Snir",

year = "1993",

month = jan,

day = "7",

doi = "10.1145/174130.174131",

language = "English (US)",

volume = "40",

pages = "421--453",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery",

number = "3",

}

TY - JOUR

T1 - Random Walks on Weighted Graphs and Applications to on-line Algorithms

AU - Coppersmith, Don

AU - Doyle, Peter

AU - Raghavan, Prabhakar

AU - Snir, Marc

PY - 1993/1/7

Y1 - 1993/1/7

N2 - The design and analysis of randomized on-line algorithms are studied. This problem is shown to be closely related to the synthesis of random wdlks on graphs with positive real costs on their edges. A theory is developed for the synthesis of such wdlks, and it is employed to design competitive on-line algorithms.

AB - The design and analysis of randomized on-line algorithms are studied. This problem is shown to be closely related to the synthesis of random wdlks on graphs with positive real costs on their edges. A theory is developed for the synthesis of such wdlks, and it is employed to design competitive on-line algorithms.

KW - metrical tasks

KW - server problem

UR - http://www.scopus.com/inward/record.url?scp=0027625007&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027625007&partnerID=8YFLogxK

U2 - 10.1145/174130.174131

DO - 10.1145/174130.174131

M3 - Article

AN - SCOPUS:0027625007

SN - 0004-5411

VL - 40

SP - 421

EP - 453

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 3

ER -

Random Walks on Weighted Graphs and Applications to on-line Algorithms

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this