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

DOI10.1016/0167-6377(92)90068-EzbMath0768.90079MaRDI QIDQ1200770

David P. Williamson

Publication date: 16 January 1993

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

zbMATH Keywords

asymmetric traveling salesmanHeld-Karp lower bound

Mathematics Subject Classification ID

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

Related Items (2)

Efficient optimization of the Held-Karp lower bound ⋮ Branch-and-bound for the precedence constrained generalized traveling salesman problem

Cites Work

• Minimum-weight two-connected spanning networks
• Survivable networks, linear programming relaxations and the parsimonious property
• 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
• A restricted Lagrangean approach to the traveling salesman problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Matroids and the greedy algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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