Analysis of the Held-Karp lower bound for the asymmetric TSP. (English) Zbl 0768.90079

Summary: We show that the Held-Karp lower bound for the asymmetric traveling salesman problem (ATSP) dominates the Balas-Christofides lower bound. For the ATSP with triangle inequality, we show that it is also greater than \((1/[\lceil\log n\rceil)Z_{\text{TSP}}\), where \(Z_{\text{TSP}}\) is the cost of the optimal tour. In the course of proving these results, we provide alternate characterizations of the Held-Karp lower bound and prove that on instances which obey the triangle inequality, the lower bound is monotonic with respect to the set of nodes included.


90C35 Programming involving graphs or networks
90C05 Linear programming
Full Text: DOI


[1] Balas, E; Christofides, N, A restricted Lagrangean approach to the traveling salesman problem, Math. programming, 21, 19-46, (1981) · Zbl 0461.90068
[2] Balas, E; Toth, P, Branch and bound methods, (), Chapter 10 · Zbl 0568.90068
[3] Christofides, N, Worst case analysis of a new heuristic for the traveling salesman problem, ()
[4] Christofides, N, The travelling salesman problem, () · Zbl 0506.90059
[5] Edmonds, J, Matroids and the greedy algorithm, Math. programming, 1, 127-136, (1971) · Zbl 0253.90027
[6] Frank, A, On connectivity properties of Eulerian digraphs, Annals of disc. math., 41, 179-194, (1989)
[7] Frieze, A.M; Galbiati, G; Maffioli, F, On the worst-case performance of some algorithms for the asymmetric traveling salesman problem, Networks, 12, 23-39, (1982) · Zbl 0478.90070
[8] Geoffrion, A.M, Lagrangean relaxation for integer programming, Math. programming study, 2, 82-114, (1974) · Zbl 0395.90056
[9] Goemans, M.X; Bertsimas, D.J, Survivable networks, linear programming relaxations and the parsimonious property, () · Zbl 0790.90072
[10] Goemans, M.X; Bertsimas, D.J, Probabilistic analysis of the held and karp lower bound for the Euclidean traveling salesman problem, Math. oper. res., 16, 72-89, (1991) · Zbl 0733.90072
[11] Held, M; Karp, R.M, The traveling-salesman problem and minimum spanning trees, Oper. res., 18, 1138-1162, (1970) · Zbl 0226.90047
[12] D.S. Johnson, personal communication, 1989.
[13] Monma, C.L; Munson, B.S; Pulleyblank, W.R, Minimum-weight two-connected spanning networks, Math. programming, 46, 153-171, (1990) · Zbl 0689.90071
[14] Shmoys, D.B; Williamson, D.P, Analyzing the held-karp TSP bound: A monotonicity property with application, Inform. process. lett., 35, 281-285, (1990) · Zbl 0698.68050
[15] Williamson, D.P, Analysis of the held-karp heuristic for the traveling salesman problem, (), Also appears as Tech Report MIT/LCS/TR-479
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.