Efficient optimization of the Held–Karp lower bound
Open Journal of Mathematical Optimization, Volume 2 (2021), article no. 9, 17 p.

Given a weighted undirected graph G=(V,E), the Held–Karp lower bound for the Traveling Salesman Problem (TSP) is obtained by selecting an arbitrary vertex p ¯V, by computing a minimum cost tree spanning V{p ¯} and adding two minimum cost edges adjacent to p ¯. In general, different selections of vertex p ¯ provide different lower bounds. In this paper it is shown that the selection of vertex p ¯ can be optimized, to obtain the largest possible Held–Karp lower bound, with the same worst-case computational time complexity required to compute a single minimum spanning tree. Although motivated by the optimization of the Held–Karp lower bound for the TSP, the algorithm solves a more general problem, allowing for the efficient pre-computation of alternative minimum spanning trees in weighted graphs where any vertex can be deleted.

Published online:
DOI: https://doi.org/10.5802/ojmo.11
Keywords: Traveling salesman problem, Minimum spanning tree, Held–Karp lower bound, Union-Find data-structure.
     author = {Giovanni Righini},
     title = {Efficient optimization of the {Held{\textendash}Karp} lower bound},
     journal = {Open Journal of Mathematical Optimization},
     eid = {9},
     publisher = {Universit\'e de Montpellier},
     volume = {2},
     year = {2021},
     doi = {10.5802/ojmo.11},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.11/}
Giovanni Righini. Efficient optimization of the Held–Karp lower bound. Open Journal of Mathematical Optimization, Volume 2 (2021), article  no. 9, 17 p. doi : 10.5802/ojmo.11. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.11/

[1] David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, 2006 | Zbl 1130.90036

[2] Pascal Benchimol; Jean-Charles Régin; Louis-Martin Rousseau; Michel Rueher; Willem-Jan van Hoeve Improving the Held and Karp Approach with Constraint Programming, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2010 (Lecture Notes in Computer Science), Volume 6140, Springer, 2010, pp. 40-44 | Article | Zbl 1285.68149

[3] Chandra Chekuri; Kent Quanrud Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time, Proceedings of the 58 t h Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2017, pp. 789-800

[4] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein Introduction to Algorithms, MIT Press, 2009 | Zbl 1187.68679

[5] The Traveling Salesman Problem and Its Variations (Gregory Gutin; Abraham P. Punnen, eds.), Springer, 2007 | Zbl 1113.90134

[6] Michael Held; Richard M. Karp The Traveling-Salesman Problem and Minimum Spanning Trees, Oper. Res., Volume 18 (1970), pp. 1138-1162 | Article | MR 278710 | Zbl 0226.90047

[7] Keld Helsgaun An effective implementation of the Lin-Kernighan traveling salesman heuristic, Eur. J. Oper. Res., Volume 126 (2000), pp. 106-130 | Article | MR 1781609 | Zbl 0969.90073

[8] Christine L. Valenzuela; Antonia J. Jones Estimating the Held-Karp lower bound for the geometric TSP, Eur. J. Oper. Res., Volume 102 (1997), pp. 157-175 | Article | Zbl 0948.90034

[9] Ton Volgenant; Roy Jonker A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, Eur. J. Oper. Res., Volume 9 (1982), pp. 83-89 | Article | MR 640030 | Zbl 0471.90088

[10] David P. Williamson Analysis of the Held-Karp lower bound for the asymmetric TSP, Oper. Res. Lett., Volume 12 (1992), pp. 83-88 | Article | MR 1188370 | Zbl 0768.90079

Cited by document(s). Sources: