Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
DOI10.1137/19M1245840zbMath1434.90169arXiv1902.06808OpenAlexW2996251045WikidataQ126589885 ScholiaQ126589885MaRDI QIDQ5206234
David P. Williamson, Samuel C. Gutekunst
Publication date: 18 December 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.06808
traveling salesman problemapproximation algorithmsintegrality gapcirculantlinear program relaxationsubtour LP
Programming involving graphs or networks (90C35) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- New inapproximability bounds for TSP
- A comparison of lower bounds for the symmetric circulant traveling salesman problem
- Survivable networks, linear programming relaxations and the parsimonious property
- Pyramidal tours and the traveling salesman problem
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- Hardness results and spectral techniques for combinatorial problems on circulant graphs
- Efficiently solvable special cases of bottleneck travelling salesman problems
- Efficiently solvable special cases of hard combinatorial optimization problems
- Hamiltonian cycles in circulant digraphs with two stripes
- Worst-case analysis of a new heuristic for the travelling salesman problem
- \(\frac{13}{9}\)-approximation for graphic TSP
- Relaxations of Combinatorial Problems Via Association Schemes
- The Design of Approximation Algorithms
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Removing and Adding Edges for the Traveling Salesman Problem
- Toeplitz and Circulant Matrices: A Review
- 8/7-approximation algorithm for (1,2)-TSP
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- On the symmetric travelling salesman problem: A computational study
- Heuristic analysis, linear programming and branch and bound
- Small Travelling Salesman Polytopes
- The Crown Inequalities for the Symmetric Traveling Salesman Polytope
- Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
- Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
- The Traveling Salesman Problem with Distances One and Two
- Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
- Solution of a Large-Scale Traveling-Salesman Problem
- The Travelling Salesman Problem in symmetric circulant matrices with two stripes
- A Randomized Rounding Approach to the Traveling Salesman Problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
