The asymmetric bottleneck traveling salesman problem: Algorithms, complexity and empirical analysis

摘要

We consider the asymmetric bottleneck traveling salesman problem on a complete directed graph on n nodes. Various lower bound algorithms are proposed and the relative strengths of each of these bounds are examined using theoretical and experimental analysis. A polynomial time [n/2]-approximation algorithm is presented when the edge-weights satisfy the triangle inequality. We also present a very efficient heuristic algorithm that produced provably optimal solutions for 270 out of 331 benchmark test instances. Our algorithms are applicable to the maxmin version of the problem, known as the maximum scatter TSP. Extensive experimental results on these instances are also given.