The travelling salesman problem: New solvable cases and linkages with the development of approximation algorithms

We identify new solvable cases of the travelling salesman problem (TSP) by an indirect analysis that has useful consequences. First, we develop new procedures for the TSP that require only linear time to execute and yield TSP tours that are better than an exponential number of alternative tours. We then identify special subgraphs, easily generated, so that our method yields these outcomes for every instance of these subgraphs. Finally, when the associated costs satisfy prescribed conditions, we show the solutions produced by these algorithms are optimal and thus we have new solvable cases of the TSP. Besides possible practical applications to problems that may exhibit these cost conditions, our algorithms may also be applied as subroutines within more complex metaheuristics. Our methods extend in a natural way to bottleneck TSP formulations, and their underlying results raise new theoretical questions about the analysis of heuristics for hard combinatorial problems.