A simple LP relaxation for the asymmetric traveling salesman problem

DOI10.1007/S10107-012-0544-9MaRDI QIDQ378136zbMATH OpenOpenAlexFDO

Authors Thành Nguyen

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)

Recommendations

• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• scientific article; zbMATH DE number 1445294
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints

Cites work

• scientific article; zbMATH DE number 1305546 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Survivable network design with degree or order constraints
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling salesman problem and its variations

Cited in

(7)

• scientific article; zbMATH DE number 1445294 (Why is no real title available?)
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• LP-based solution methods for the asymmetric TSP
• Relaxation of the polytope of the asymmetric travelling salesman problem on the basis of the cone of generalized Supnick's matrices
• On the LP relaxation of the asymmetric traveling salesman path problem
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378136)