On the power of lookahead in on-line server routing problems

被引：13

作者：

Allulli, Luca ^{[1
]}

Ausiello, Giorgio ^{[1
]}

Bonifaci, Vincenzo ^{[1
,2
]}

Laura, Luigi ^{[1
]}

机构：

[1] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, I-00185 Rome, Italy

[2] Univ Aquila, Dipartimento Ingn Elettr, I-67040 Laquila, Italy

来源：

THEORETICAL COMPUTER SCIENCE | 2008年 / 408卷 / 2-3期

关键词：

On-line algorithms; Competitive analysis; Lookahead; Traveling salesman problem;

D O I：

10.1016/j.tcs.2008.08.003

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the usefulness of lookahead in on-line server routing problems: if an on-line algorithm is not only informed about the requests released so far, but also has a limited ability to foresee future requests, what is the improvement that can be achieved in terms of the competitive ratio? We consider several on-line server routing problems in this setting, such as the on-line traveling salesman and the on-line traveling repairman problem. We show that the influence of lookahead can change considerably depending on the particular objective function and metric space considered. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：116 / 128

页数：13

共 32 条

[1] THE COMPLEXITY OF THE TRAVELING REPAIRMAN PROBLEM [J].

AFRATI, F ;

COSMADAKIS, S ;

PAPADIMITRIOU, CH ;

PAPAGEORGIOU, G ;

PAPAKOSTANTINOU, N .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1986, 20 (01) :79-87

[2] A competitive analysis of the list update problem with lookahead [J].

Albers, S .

THEORETICAL COMPUTER SCIENCE, 1998, 197 (1-2) :95-109

[3] On the influence of lookahead in competitive paging algorithms [J].

Albers, S .

ALGORITHMICA, 1997, 18 (03) :283-305

[4]

ALLULLI L, 2005, TR0205 U ROM LA SAP

[5]

Ascheuer N, 2000, LECT NOTES COMPUT SC, V1770, P639

[6] Algorithms for the on-line Quota Traveling Salesman Problem [J].

Ausiello, G ;

Demange, M ;

Laura, L ;

Paschos, V .

INFORMATION PROCESSING LETTERS, 2004, 92 (02) :89-94

[7] Algorithms for the on-line travelling salesman [J].

Ausiello, G ;

Feuerstein, E ;

Leonardi, S ;

Stougie, L ;

Talamo, M .

ALGORITHMICA, 2001, 29 (04) :560-581

[8]

Ausiello G, 2006, LECT NOTES COMPUT SC, V3959, P1

[9] The on-line asymmetric traveling salesman problem [J].

Ausiello, Giorgio ;

Bonifaci, Vincenzo ;

Laura, Luigi .

JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (02) :290-298

[10] The online TSP against fair adversaries [J].

Blom, M ;

Krumke, SO ;

de Paepe, WE ;

Stougie, L .

INFORMS JOURNAL ON COMPUTING, 2001, 13 (02) :138-148

← 1 2 3 4 →