@inproceedings{d1044bb4616547e3857ddde7dbbf555c,
title = "Online k-server routing problems",
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 average completion time (k-Traveling Repairman Problem). We give competitive algorithms, resource augmentation results and lower bounds for k-server routing problems on several classes of metric spaces. Surprisingly, in some cases the competitive ratio is dramatically better than that of the corresponding single server problem. Namely, we give a 1+O((logk)/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 similar results cannot hold for the Euclidean plane.",
author = "V. Bonifaci and L. Stougie",
year = "2007",
doi = "10.1007/11970125\_7",
language = "English",
isbn = "978-3-540-69513-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "83--94",
editor = "T. Erlebach and C. Kaklamanis",
booktitle = "Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA 2006) 14-15 September 2006, Z{\"u}rich, Switzerland",
address = "Germany",
note = "conference; WAOA 2006, Zurich, Switzerland; 2006-09-14; 2006-09-15 ; Conference date: 14-09-2006 Through 15-09-2006",
}