The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
From MaRDI portal
Publication:4577740
DOI10.1137/17M1154722zbMath1402.90114arXiv1710.08455WikidataQ129483659 ScholiaQ129483659MaRDI QIDQ4577740
Samuel C. Gutekunst, David P. Williamson
Publication date: 3 August 2018
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.08455
Semidefinite programming (90C22) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP, Gaddum's test for symmetric cones, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- Semidefinite programs and association schemes
- \(\frac{13}{9}\)-approximation for graphic TSP
- Convex Relaxations and Integrality Gaps
- 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
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- On Semidefinite Programming Relaxations of the Traveling Salesman Problem
- Heuristic analysis, linear programming and branch and bound
- Cones of Matrices and Set-Functions and 0–1 Optimization
- 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
- A General Approximation Technique for Constrained Forest Problems
- Solution of a Large-Scale Traveling-Salesman Problem
- On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
