ALCOMFT-TR-03-8

Vladimir Deineko and Alexander Tiskin
The Double-Tree Approximation for Metric TSP: Is The Best Good Enough?
Warwick. Work packages 3, 4 and 5. June 2003.

Abstract: The Metric Travelling Salesman Problem (TSP) is a classical NP-hard optimisation problem. The double-tree heuristic allows one to approximate the solution of the Metric TSP within a factor of 2, by picking an arbitrary solution from a restricted space of solutions to the original problem. Such an approach raises two natural questions: can we find efficiently a solution that is optimal in the restricted space? will this optimal solution provide a better approximation ratio than an arbitrary solution? In 1998, Burkard et al\@. answered the first question in the affirmative, by presenting an algorithm that finds the optimal double-tree solution to Metric TSP in time O(2^dn³) and space O(n²), where d is the maximum node degree in the corresponding minimal spanning tree (e.g. in the Euclidean case, d <= 6). We improve these bounds to time O(2^dn²) and space O(4^dn). We also give a partial answer to the second question, by presenting a lower bound of 1.666 on the approximation ratio of the optimal double-tree solution. Computational experiments show that the optimal double-tree algorithm is practical, providing one of the best known tour-constructing heuristics.

Postscript file: ALCOMFT-TR-03-8.ps.gz (97 kb).