Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishIn 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((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 similar results cannot hold for the Euclidean plane. © Springer-Verlag Berlin Heidelberg 2006.
Bonifaci, V., & Stougie, L. (2007). Online k-server routing problems. In Proc. 4th Int. Workshop on Approximation and Online Algorithms (pp.83-94). Berlin : Springer Verlag.
| Titolo: | Online k-server routing problems |
| Autori: | |
| Data di pubblicazione: | 2007 |
| Serie: | |
| Citazione: | Bonifaci, V., & Stougie, L. (2007). Online k-server routing problems. In Proc. 4th Int. Workshop on Approximation and Online Algorithms (pp.83-94). Berlin : Springer Verlag. |
| Handle: | http://hdl.handle.net/11590/379866 |
| ISBN: | 978-3-540-69513-4 |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11590/379866
Copyright © 2021