The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem

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

zbMATH Keywords

semidefinite programmingtraveling salesman problemapproximation algorithms

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

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

This page was built for publication: The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem