News from the online traveling repairman

ABSTRACT. The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is, the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem OLTRP requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie [FS00] presented a 9-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from onlinescheduling to obtain an 8-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio 4 of ≈ 5.7708 against an oblivious adversary. All of our results also hold for the ln 2 “dial-a-ride ” generalization of the OLTRP, where objects have to be picked up and delivered by a server. 1