On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy

DOI10.1007/s10107-015-0947-5zbMath1346.90569OpenAlexW1581729816MaRDI QIDQ312658

Joseph Cheriyan, Sahil Singla, Zhihan Gao, Konstantinos Georgiou

Publication date: 16 September 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-015-0947-5

zbMATH Keywords

asymmetric TSPintegrality ratiosSherali-Adams hierarchy

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (1)

Integrality gaps for colorful matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• On the approximability of the traveling salesman problem
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Convex Relaxations and Integrality Gaps
• New Inapproximability Bounds for TSP
• Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy
• Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
• Improved Inapproximability for TSP
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Integrality gaps for Sherali-Adams relaxations
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

This page was built for publication: On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy