Online k-server routing problems

V. Bonifaci, L. Stougie

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

7 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)470-485
TijdschriftTheory of Computing Systems
Volume45
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2009

Vingerafdruk

Duik in de onderzoeksthema's van 'Online k-server routing problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit