Online algorithms: a survey

被引：147

作者：

Albers, S ^{[1
]}

机构：

[1] Univ Freiburg, Inst Informat, D-79110 Freiburg, Germany

来源：

MATHEMATICAL PROGRAMMING | 2003年 / 97卷 / 1-2期

关键词：

D O I：

10.1007/s10107-003-0436-0

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

During the last 15 years online algorithms have received considerable research interest. In this survey we give an introduction to the competitive analysis of online algorithms and present important results. We study interesting application areas and identify open problems.

引用

页码：3 / 26

页数：24

共 99 条

[1] Competitive analysis of randomized paging algorithms [J].

Achlioptas, D ;

Chrobak, M ;

Noga, J .

THEORETICAL COMPUTER SCIENCE, 2000, 234 (1-2) :203-218

[2] Average case analyses of list update algorithms, with applications to data compression [J].

Albers, S ;

Mitzenmacher, M .

ALGORITHMICA, 1998, 21 (03) :312-318

[3] On generalized connection caching [J].

Albers, S .

THEORY OF COMPUTING SYSTEMS, 2002, 35 (03) :251-267

[4] A COMBINED BIT AND TIMESTAMP ALGORITHM FOR THE LIST UPDATE PROBLEM [J].

ALBERS, S ;

VONSTENGEL, B ;

WERCHNER, R .

INFORMATION PROCESSING LETTERS, 1995, 56 (03) :135-139

[5] Better bounds for online scheduling [J].

Albers, S .

SIAM JOURNAL ON COMPUTING, 1999, 29 (02) :459-473

[6] Improved randomized on-line algorithms for the list update problem [J].

Albers, S .

SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :682-693

[7]

Albers S, 2002, P 34 ANN ACM S THEOR, P258

[8]

ALBERS S, 2003, P 14 ACM SIAM S THEO

[9]

ALBERS S, 2002, P 34 ANN ACM S THEOR, P134

[10] A new lower bound for the list update problem in the partial cost model [J].

Ambühl, C ;

Gärtner, B ;

von Stengel, B .

THEORETICAL COMPUTER SCIENCE, 2001, 268 (01) :3-16

← 1 2 3 4 5 6 7 8 9 10 →