A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem

DOI10.1007/978-3-540-85363-3_17MaRDI QIDQ3541797zbMATH OpenOpenAlexFDO

Authors

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_17

zbMATH Keywords

ATSPLP relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A simple LP relaxation for the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 1445294
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• LP-based solution methods for the asymmetric TSP

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximating minimum bounded degree spanning trees to within one of optimal
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 3156381 (Why is no real title available?)
• scientific article; zbMATH DE number 1305546 (Why is no real title available?)
• scientific article; zbMATH DE number 2079394 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• scientific article; zbMATH DE number 5485591 (Why is no real title available?)
• 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
• Survivable network design with degree or order constraints
• The traveling salesman problem and its variations
• The Traveling-Salesman Problem and Minimum Spanning Trees

Cited in

(8)

• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• On the LP relaxation of the asymmetric traveling salesman path problem
• scientific article; zbMATH DE number 6347354 (Why is no real title available?)
• A simple LP relaxation for the asymmetric traveling salesman problem
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• scientific article; zbMATH DE number 1445294 (Why is no real title available?)
• On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
• LP-based solution methods for the asymmetric TSP

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 Q3541797)