RANDOM-WALKS ON WEIGHTED GRAPHS AND APPLICATIONS TO ONLINE ALGORITHMS

被引：45

作者：

COPPERSMITH, D ^{[1
]}

DOYLE, P ^{[1
]}

RAGHAVAN, P ^{[1
]}

SNIR, M ^{[1
]}

机构：

[1] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

JOURNAL OF THE ACM | 1993年 / 40卷 / 03期

关键词：

ALGORITHMS; THEORY; METRICAL TASKS; ONLINE ALGORITHMS; RANDOM WALKS; SERVER PROBLEM;

D O I：

10.1145/174130.174131

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

引用

页码：421 / 453

页数：33

共 23 条

[1]

BAEZAYATES RA, 1987, CS8768 U WAT COMP SC

[2] AN INEQUALITY WITH APPLICATIONS TO STATISTICAL ESTIMATION FOR PROBABILISTIC FUNCTIONS OF MARKOV PROCESSES AND TO A MODEL FOR ECOLOGY [J].

BAUM, LE ;

EAGON, JA .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1967, 73 (03) :360-&

[3]

BENDAVID S, 1990, 22ND P ANN ACM S THE, P379

[4]

BERMAN P, 1990, 1ST P ANN ACM SIAM S, P280

[5]

BORODIN A, 1987, 19TH P ANN ACM S THE, P373

[6] ON THE ALGEBRA OF NETWORKS [J].

BOTT, R ;

DUFFIN, RJ .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1953, 74 (JAN) :99-109

[7]

CHANDRA AK, 1989, 21ST P ANN ACM S THE, P574, DOI DOI 10.1145/73007.73062

[8] AN OPTIMAL ONLINE ALGORITHM FOR K-SERVERS ON TREES [J].

CHROBAK, M ;

LARMORE, LL .

SIAM JOURNAL ON COMPUTING, 1991, 20 (01) :144-148

[9]

CHROBAK M, 1990, 1ST P ANN ACM SIAM S, P291

[10]

DOYLE PG, 1984, RANDOM WALKS ELECTRI

← 1 2 3 →