A domination algorithm for \0,1\-instances of the travelling salesman problem

DOI10.1002/RSA.20600zbMATH Open1372.90095arXiv1401.4931OpenAlexW2180527134MaRDI QIDQ2811158FDOQ2811158

Viresh Patel, Daniela Kühn, Deryk Osthus

Publication date: 10 June 2016

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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(-(logn{)}^C)$ in the result above.

Full work available at URL: https://arxiv.org/abs/1401.4931

Recommendations

• The traveling salesman problem: new polynomial approximation algorithms and domination analysis
• Domination analysis of some heuristics for the traveling salesman problem
• TSP heuristics: domination analysis and complexity
• scientific article
• TSP tour domination and Hamilton cycle decompositions of regular digraphs

zbMATH Keywords

algorithmstravelling salesman problemcombinatorial dominance

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Boolean programming (90C09)

Cites Work

• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Maximum matching and a polyhedron with 0,1-vertices
• On the complexity of \(k\)-SAT
• On a combinatorial game
• P-Complete Approximation Problems
• On the approximability of the traveling salesman problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Domination analysis of combinatorial optimization problems.
• Domination analysis of greedy heuristics for the frequency assignment problem.
• TSP heuristics: domination analysis and complexity
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Algorithms with large domination ratio
• Combinatorial dominance guarantees for problems with infeasible solutions
• TSP tour domination and Hamilton cycle decompositions of regular digraphs
• Note on upper bounds for TSP domination number

Cited In (3)

• Parameterized Traveling Salesman Problem: Beating the Average
• Domination analysis of combinatorial optimization problems.
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number

This page was built for publication: A domination algorithm for \(\{0,1\}\)-instances of the travelling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811158)