## News from the Online Traveling Repairman

Please always quote using this URN: urn:nbn:de:0297-zib-5767

- 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 presented a $9$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an $8$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of $\frac{4}{\ln 2}\approx 5.7708$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.

Author: | Sven Krumke |
---|---|

Document Type: | ZIB-Report |

Tag: | Competitive Analysis; Dial-a-Ride-Problem; Latency; Traveling Repairman |

MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |

CCS-Classification: | F. Theory of Computation / F.1 COMPUTATION BY ABSTRACT DEVICES / F.1.2 Modes of Computation |

Date of first Publication: | 2000/03/23 |

Series (Serial Number): | ZIB-Report (00-08) |

ZIB-Reportnumber: | 00-08 |

Published in: | A rev. vers. - together with W. E. de Paepe and D. Poensgen - appeared in: Proc. of the 26th Int. Symp. on Math. Foundations of Computer Science, Springer 2001, LNCS, 2136, pp. 487-499 and in Theoretical Computer Sceince 295 (2003 pp. 279-294 |