A domination algorithm for {0,1}-instances of the travelling salesman problem
From MaRDI portal
Publication:2811158
DOI10.1002/rsa.20600zbMath1372.90095arXiv1401.4931OpenAlexW2180527134MaRDI QIDQ2811158
Viresh Patel, Daniela Kühn, Deryk Osthus
Publication date: 10 June 2016
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.4931
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
- 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
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- On the approximability of the traveling salesman problem
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- On maximal paths and circuits of graphs
- P-Complete Approximation Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
- Algorithms with large domination ratio
- Combinatorial dominance guarantees for problems with infeasible solutions
- Maximum matching and a polyhedron with 0,1-vertices
- On a combinatorial game
- TSP tour domination and Hamilton cycle decompositions of regular digraphs
- On the complexity of \(k\)-SAT
