A domination algorithm for {0, 1}‐instances of the travelling salesman problem1. Issue 3 (8th October 2015)

• Record Type: Journal Article
• Authors: Kühn, Daniela; Osthus, Deryk; Patel, Viresh
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 427
• Page End: 453
• Publication Date: 2015-10-08
• Subjects: travelling salesman problem -- algorithms -- combinatorial dominance; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20600
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 − o ( 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. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 427–453, 2016