Random walks on weighted graphs, and applications to on-line algorithms.

Don Coppersmith; Peter Doyle; Prabhakar Raghavan; Marc Snir

Random walks on weighted graphs, and applications to on-line algorithms.

Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.

Original language	English (US)
Title of host publication	Proc 22nd Annu ACM Symp Theory Comput
Publisher	Publ by ACM
Pages	369-378
Number of pages	10
ISBN (Print)	0897913612
State	Published - 1990
Externally published	Yes
Event	Proceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA Duration: May 14 1990 → May 16 1990

Other

Other	Proceedings of the 22nd Annual ACM Symposium on Theory of Computing
City	Baltimore, MD, USA
Period	5/14/90 → 5/16/90

ASJC Scopus subject areas

Engineering(all)

Library availability

Discover UIUC Full Text

Cite this

@inproceedings{6851dc3ba91044d6a979161445dd6e32,

title = "Random walks on weighted graphs, and applications to on-line algorithms.",

abstract = "We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.",

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

year = "1990",

language = "English (US)",

isbn = "0897913612",

pages = "369--378",

booktitle = "Proc 22nd Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

note = "Proceedings of the 22nd Annual ACM Symposium on Theory of Computing ; Conference date: 14-05-1990 Through 16-05-1990",

}

TY - GEN

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 - 1990

Y1 - 1990

N2 - We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.

AB - We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.

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

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

M3 - Conference contribution

AN - SCOPUS:0024984003

SN - 0897913612

SP - 369

EP - 378

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -

Random walks on weighted graphs, and applications to on-line algorithms.

Abstract

Other

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this