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 proceedingConference 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 languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages369-378
Number of pages10
ISBN (Print)0897913612
StatePublished - 1990
Externally publishedYes
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Random walks on weighted graphs, and applications to on-line algorithms.'. Together they form a unique fingerprint.

Cite this