ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS

被引：148

作者：

BENDAVID, S

BORODIN, A

KARP, R

TARDOS, G

WIGDERSON, A

机构：

[1] UNIV TORONTO, DEPT COMP SCI, TORONTO M5S 1A4, ON, CANADA

[2] UNIV CALIF BERKELEY, BERKELEY, CA 94720 USA

[3] INT COMP SCI INST, BERKELEY, CA 94704 USA

[4] EOTVOS LORAND UNIV, H-1364 BUDAPEST, HUNGARY

[5] HEBREW UNIV JERUSALEM, JERUSALEM, ISRAEL

来源：

ALGORITHMICA | 1994年 / 11卷 / 01期

关键词：

ONLINE ALGORITHMS; COMPETITIVE ANALYSIS; RANDOMIZED ALGORITHMS; GAME THEORY;

D O I：

10.1007/BF01294260

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient ''simulation'' of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.

引用

页码：2 / 14

页数：13

共 17 条

[1]

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

[2]

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

[3]

BORODIN A, 1992, J ASSOC COMPUT MACH, V39, P743

[4]

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

[5]

COPPERSMITH D, 1990, 22ND P ANN ACM S THE, P369

[6]

DENG X, 1991, 23RD P ANN ACM S THE, P289

[7] COMPETITIVE PAGING-ALGORITHMS [J].

FIAT, A ;

KARP, RM ;

LUBY, M ;

MCGEOCH, LA ;

SLEATOR, DD ;

YOUNG, NE .

JOURNAL OF ALGORITHMS, 1991, 12 (04) :685-699

[8]

FIAT A, 1990, ANN IEEE SYMP FOUND, P454, DOI 10.1109/FSCS.1990.89566

[9]

Gale D, 1953, CONTRIBUTIONS THEORY, V2, P245

[10]

GROVE E, 1991, 23RD P ANN ACM S THE, P260

← 1 2 →