MINIMUM TRAVELING REPAIRMAN

• INSTANCE: Graph $G=\left(V,E\right)$, start vertex $r\in V$, length $l(e)\in N$ for each $e\in E$ satisfying the triangle inequality.

• SOLUTION: A walk starting in r visiting all vertices in G, i.e., a permutation $\pi: [1..\vert V\vert\rightarrow V$ such that $\pi(1)=r$, where $\pi$ describes in which order the vertices are visited for the first time.

• MEASURE: $\sum_{v\in V} d_{\pi}(r,v)$, where $d_{\pi}(r,v)$ is the total distance traversed in the walk from r until we first visit v.

  
  

• Good News: Approximable within 10.78 [184].

• Comment: Also called the Minimum Latency Problem. For fixed-dimensional Euclidean spaces the problem is approximable within 3.59 [195] and admits a quasi polynomial PTAS [38]. Variation in which the objective is the maximum search ratio, i.e., $\max_{v\in V} d_{\pi}(r,v)/d(r,v)$ is approximable within 6 and is APX-complete [339]. Variation in which the graph metric is used (all lengths 1 or $\infty$) is approximable within 1.662 [339].