Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps

DOI10.1287/moor.2020.1100zbMath1492.90146arXiv1907.09054OpenAlexW3145869904MaRDI QIDQ5076689

Samuel C. Gutekunst, David P. Williamson

Publication date: 17 May 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingtraveling salesman problemintegrality gap

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

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
• New inapproximability bounds for TSP
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Semidefinite programming relaxations for the quadratic assignment problem
• Worst-case comparison of valid inequalities for the TSP
• Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem
• Relaxations of Combinatorial Problems Via Association Schemes
• SDP Relaxations for Some Combinatorial Optimization Problems
• The Design of Approximation Algorithms
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Assignment Problems and the Location of Economic Activities
• 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
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• The Traveling-Salesman Problem and Minimum Spanning Trees