New approximation results for the maximum scatter TSP (Q1774146)

The author considers the maximum scatter traveling salesman problem: There is an edge-weighted complete graph \(G\), find a Hamiltonian cycle such that the length of a shortest edge in your cycle is maximum. The problem is also known under the name max-min 1-neighbour TSP. In the max-min \(m\)-neighbour TSP the problem is to find a Hamiltonian cycle (path) such that the minimum distance between any point and all of its \(m\) neighbours on the cycle is maximized. The poblem in general is NP-complete and no constant factor approximation exists unless P = NP. The author gives an \(O(n^2.5)\) time approximation for the max-min 2-neighbour TSP with triangle inequality. The paper contains a factor 12 approximation for the path version and a factor 18 approximation for the cycle version The author describes new algorithms for \(n=3k\) and the path version and for all cases of \(n\) and the cycle version and the remaining cases and the path version. Two new algorithms for the case \(n=3k+1\) in the path version are provided. There is also a \(O(mn^2.5)\) time algorithm that achieves a constant approximation factor of 16 for the path version of the max-min \(m\)-neighbour TSP for certain values of \(n\) and \(m\).