MINIMUM METRIC BOTTLENECK WANDERING SALESPERSON PROBLEM

• INSTANCE: Set C of m cities, an initial city $s\in C$, a final city $f\in C$, distances $d(c_i,c_j)\in N$ satisfying the triangle inequality.

• SOLUTION: A simple path from the initial city s to the final city f passing through all cities in C, i.e., a permutation $\pi: [1..m]\rightarrow[1..m]$ such that $v_{\pi(1)}=s$ and $v_{\pi(m)}=f$.

• MEASURE: The length of the largest distance in the path, i.e.,
  
  $$\max\limits_{i\in[1..m-1]}d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right).$$
  
  

  
  

• Good News: Approximable within 2 [254].

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [254].

• Comment: The same positive and negative results hold even if X is a set of point in d-dimensional space with the $L_1$ or $L_\infty$ metric. If the $L_2$ metric is used then the upper bound is 1.969 [152]. The corresponding maximization problem called MAXIMUM SCATTER TSP, where the length of the shortest distance in the path is maximized, is approximable within 2, but not approximable within $2-\varepsilon$ for any $\varepsilon >0$ [26].

• Garey and Johnson: ND24