A simple LP relaxation for the asymmetric traveling salesman problem

DOI10.1007/s10107-012-0544-9zbMath1280.90100OpenAlexW2010462135MaRDI QIDQ378136

Mohammad Hasan, H. S. Yoon

Publication date: 11 November 2013

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

Full work available at URL: https://doi.org/10.1007/s10107-012-0544-9

zbMATH Keywords

traveling salesman problemextreme solutionssubtour elimination linear program relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• The traveling salesman problem and its variations
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Survivable Network Design with Degree or Order Constraints
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Solution of a Large-Scale Traveling-Salesman Problem
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: A simple LP relaxation for the asymmetric traveling salesman problem