A simple LP relaxation for the asymmetric traveling salesman problem

DOI10.1007/S10107-012-0544-9zbMATH Open1280.90100OpenAlexW2010462135MaRDI QIDQ378136FDOQ378136

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

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

zbMATH Keywords

traveling salesman problemextreme solutionssubtour elimination linear program relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

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

Cited In (8)

• Title not available (Why is that?)
• 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
• The asymmetric traveling salesman path LP has constant integrality ratio
• 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)