News from the online traveling repairman

In the traveling repairman problem (TRP), a tour must be found through every one of a set of points (cities) in some metric space such that the weighted sum of completion times of the cities is minimized. Given a tour, the completion time of a city is the time traveled on the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities arrive online while the repairman is traveling. We analyze the performance of algorithms for the online problem using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. We show how to use techniques from online-scheduling to obtain a deterministic algorithm with a competitive ratio of (1 + root2)(2) < 5.8285 for the OLTRP in general metric spaces. We also present a randomized algorithm which achieves a competitive ratio of 4/ln 3 < 3.6410 against an oblivious adversary. Our results extend to the "dial-a-ride" generalization L-OLDARP of the OLTRP, where objects have to be picked up and delivered by a server. This improves upon the previously best competitive ratio of 9 for the OLTRP on the real line and, moreover, the results are valid for any metric space. For the case of the L-OLDARP our algorithms are the first competitive algorithms. We also derive the first lower bounds for the competitive ratio of randomized algorithms for the OLTRP and the L-OLDARP against an oblivious adversary. Our lower bounds are (In 16 + 1)/(ln 16-1) > 2.1282 for the L-OLDARP on the line, (4e-5)/(2e-3) > 2.41041 for the L-OLDARP on general metric spaces, 2 for the OLTRP on the line, and 7/3 for the OLTRP on general metric spaces. (C) 2002 Elsevier Science B.V. All rights reserved.