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. © 2008 Elsevier B.V. All rights reserved.
On the power of lookahead in on-line server routing problems / Ausiello, Giorgio; Luca, Allulli; Bonifaci, Vincenzo; Laura, Luigi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 408:2-3(2008), pp. 116-128. [10.1016/j.tcs.2008.08.003]
On the power of lookahead in on-line server routing problems
AUSIELLO, Giorgio;BONIFACI, VINCENZO;LAURA, Luigi
2008
Abstract
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. © 2008 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
