Analysis of the Held-Karp lower bound for the asymmetric TSP

DOI10.1016/0167-6377(92)90068-EMaRDI QIDQ1200770zbMATH OpenFDO

Authors David P. Williamson

Publication date 16 January 1993

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(92)90068-E

zbMATH Keywords

asymmetric traveling salesmanHeld-Karp lower bound

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35)

Recommendations

• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 871931
• Efficient optimization of the Held-Karp lower bound

Cites work

• A restricted Lagrangean approach to the traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• scientific article; zbMATH DE number 3908167 (Why is no real title available?)
• scientific article; zbMATH DE number 4103110 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3799403 (Why is no real title available?)
• Matroids and the greedy algorithm
• Minimum-weight two-connected spanning networks
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
• Survivable networks, linear programming relaxations and the parsimonious property
• The Traveling-Salesman Problem and Minimum Spanning Trees

Cited in

(7)

• Estimating the Held-Karp lower bound for the geometric TSP
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Branch-and-bound for the precedence constrained generalized traveling salesman problem
• Efficient optimization of the Held-Karp lower bound
• Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
• scientific article; zbMATH DE number 871931 (Why is no real title available?)
• Analyzing the Held-Karp TSP bound: A monotonicity property with application

This page was built for publication: Analysis of the Held-Karp lower bound for the asymmetric TSP

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