Speedup in the Traveling Repairman Problem with Unit Time Windows

Abstract

The input to the unrooted traveling repairman problem is an undirected metric graph and a subset of nodes, each of which has a time window of unit length. Given that a repairman can start at any location, the goal is to plan a route that visits as many nodes as possible during their respective time windows. A polynomial-time bicriteria approximation algorithm is presented for this problem, gaining an increased fraction of repairman visits for increased speedup of repairman motion. For speedup $s$, we find a $6\gamma /(s+1)$-approximation for $s$ in the range $1\le s\le 2$ and a $4\gamma /s$-approximation for $s$ in the range $2\le s\le 4$, where $\gamma =1$ on tree-shaped networks and $\gamma =2+\epsilon$ on general metric graphs.

16 pages, 3 figures

References in corpus (1)

• Approximation Algorithms for Orienteering with Time Windows

Cited by in corpus (1)

• Speedup in the Traveling Repairman Problem with Constrained Time Windows