In an online k-server routing problem, a crew of k servers has to visit points in a metric space as they arrive in real time. Possible objective functions include minimizing the makespan (k-Traveling Salesman Problem) and minimizing the sum of completion times (k-Traveling Repairman Problem). We give competitive algorithms, resource augmentation results and lower bounds for k-server routing problems in a wide class of metric spaces. In some cases the competitive ratio is dramatically better than that of the corresponding single server problem. Namely, we give a 1 + O((log k)/k)-competitive algorithm for the k-Traveling Salesman Problem and the k-Traveling Repairman Problem when the underlying metric space is the real line. We also prove that a similar result cannot hold for the Euclidean plane. © Springer Science+Business Media, LLC 2008.

Bonifaci, V., Stougie, L. (2009). Online k-server routing problems. THEORY OF COMPUTING SYSTEMS, 45(3), 470-485 [10.1007/s00224-008-9103-4].

Online k-server routing problems

Bonifaci V.
;
2009

Abstract

In an online k-server routing problem, a crew of k servers has to visit points in a metric space as they arrive in real time. Possible objective functions include minimizing the makespan (k-Traveling Salesman Problem) and minimizing the sum of completion times (k-Traveling Repairman Problem). We give competitive algorithms, resource augmentation results and lower bounds for k-server routing problems in a wide class of metric spaces. In some cases the competitive ratio is dramatically better than that of the corresponding single server problem. Namely, we give a 1 + O((log k)/k)-competitive algorithm for the k-Traveling Salesman Problem and the k-Traveling Repairman Problem when the underlying metric space is the real line. We also prove that a similar result cannot hold for the Euclidean plane. © Springer Science+Business Media, LLC 2008.
Bonifaci, V., Stougie, L. (2009). Online k-server routing problems. THEORY OF COMPUTING SYSTEMS, 45(3), 470-485 [10.1007/s00224-008-9103-4].
File in questo prodotto:
File Dimensione Formato  
multiserver-tocs.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 223 kB
Formato Adobe PDF
223 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/11590/380504
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact