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

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 cons...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2008-11, Vol.408 (2), p.116-128
Main Authors: Allulli, Luca, Ausiello, Giorgio, Bonifaci, Vincenzo, Laura, Luigi
Format: Article
Language:English
Subjects:
Competitive analysis
Lookahead
On-line algorithms
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2008.08.003