New Lower Bounds for Online k-Server Routing Problems

In a k-server routing problem k ≥ 1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour, (k-Traveling Salesman Problem or k-tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-trp). Both problems, the k-tsp and the k-trp have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k> 1, in particular for randomized algorithms against an oblivious adversary. We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound of 4e−5 2e−3 ≈ 2.4104 for k-darp (the k-trp when objects need to be carried) to 3 which is currently also the best lower bound for deterministic algorithms