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.

Allulli, L., Ausiello, G., Bonifaci, V., & Laura, L. (2008). On the power of lookahead in on-line server routing problems. THEORETICAL COMPUTER SCIENCE, 408(2-3), 116-128 [10.1016/j.tcs.2008.08.003].

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

Bonifaci V.;
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.
Allulli, L., Ausiello, G., Bonifaci, V., & Laura, L. (2008). On the power of lookahead in on-line server routing problems. THEORETICAL COMPUTER SCIENCE, 408(2-3), 116-128 [10.1016/j.tcs.2008.08.003].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/380485
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 12
social impact