A Domination Algorithm for {0,1}-Instances of the Travelling Salesman Problem

作者：Kuehn Daniela; Osthus Deryk; Patel Viresh^*

来源：Random Structures and Algorithms, 2016, 48(3): 427-453.

DOI：10.1002/rsa.20600

• travelling salesman problem
• algorithms
• combinatorial dominance

We present an approximation algorithm for {0, 1}-instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial-time algorithm which has domination ratio 1 - n(-1/29). In other words, given a {0, 1}-edge-weighting of the complete graph K-n on n vertices, our algorithm outputs a Hamilton cycle H* of K-n with the following property: the proportion of Hamilton cycles of K-n whose weight is smaller than that of H* is at most n(-1/29). Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio 1/2-0(1) for arbitrary edge-weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant C such that n-1/29 cannot be replaced by exp(-(log n) C) in the result above.

• 出版日期2016-5