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 $\overline{p}\in V$, by computing a minimum cost tree spanning $V\setminus \left\{\overline{p}\right\}$ and adding two minimum cost edges adjacent to $\overline{p}$. In general, different selections of vertex $\overline{p}$ provide different lower bounds. In this paper it is shown that the selection of vertex $\overline{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.

Revised:

Accepted:

Published online:

Keywords: Traveling salesman problem, Minimum spanning tree, Held–Karp lower bound, Union-Find data-structure.

@article{OJMO_2021__2__A9_0, 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] The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, 2006 | Zbl 1130.90036

[2] 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] 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] 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] The Traveling-Salesman Problem and Minimum Spanning Trees, Oper. Res., Volume 18 (1970), pp. 1138-1162 | Article | MR 278710 | Zbl 0226.90047

[7] 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] 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] 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] 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: *