Online k-Server Routing Problems

作     者：Bonifaci, Vincenzo Stougie, Leen 

作者机构：Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Ctr Math & Comp Sci CWI Amsterdam Netherlands Univ Roma La Sapienza Dept Comp & Syst Sci Rome Italy 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2009年第45卷第3期

页      面：470-485页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：European Commission, EC, (MRTN-CT-2003-504438) Ministerie van Onderwijs, Cultuur en Wetenschap, OCW 

主　　题：Online algorithms Competitive analysis Server routing Traveling salesman Traveling repairman 

摘      要：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.