Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem (Q1079133)

The bottleneck cost of a routing in a complete digraph \(G=(V,R)\) with costs \(C: V^ 2\to V\) is the maximal element \(\max_{(i,j)\in r}c_{ij}\) of the routing r. The authors are interested in minimizing the bottleneck costs in general and under certain restrictions (given a subset of endpoints etc.). Under the assumption that C obeys the triangle inequality the following results hold: (1) there exist (polynomial) heuristics, which guarantee solutions, that have cost no more than twice the optimum; (2) these heuristics are optimal in the following sense: if any heuristic can guarantee a (2-\(\epsilon)\)-approximation \((\epsilon >0)\), then \(P=NP.\) The proofs crucially take advantage of the square \(G^ 2\) of an arbitrary graph G and the fact (due to Rardin and Lau) that it is possible to find a Hamiltonian cycle in \(G^ 2\) of any biconnected graph G in polynomial time (G given as input).