Given a weighted undirected graph , the Held–Karp lower bound for the Traveling Salesman Problem (TSP) is obtained by selecting an arbitrary vertex , by computing a minimum cost tree spanning and adding two minimum cost edges adjacent to . In general, different selections of vertex provide different lower bounds. In this paper it is shown that the selection of vertex 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:
DOI: 10.5802/ojmo.11

@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}, pages = {1--17}, publisher = {Universit\'e de Montpellier}, volume = {2}, year = {2021}, doi = {10.5802/ojmo.11}, mrnumber = {4236590}, language = {en}, url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.11/} }
TY - JOUR AU - Giovanni Righini TI - Efficient optimization of the Held–Karp lower bound JO - Open Journal of Mathematical Optimization PY - 2021 SP - 1 EP - 17 VL - 2 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.11/ DO - 10.5802/ojmo.11 LA - en ID - OJMO_2021__2__A9_0 ER -
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
[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 | DOI | Zbl
[3] Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time, Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2017, pp. 789-800 | Zbl
[4] Introduction to Algorithms, MIT Press, 2009 | Zbl
[5] The Traveling Salesman Problem and Its Variations (Gregory Gutin; Abraham P. Punnen, eds.), Springer, 2007 | Zbl
[6] The Traveling-Salesman Problem and Minimum Spanning Trees, Oper. Res., Volume 18 (1970), pp. 1138-1162 | DOI | MR | Zbl
[7] An effective implementation of the Lin-Kernighan traveling salesman heuristic, Eur. J. Oper. Res., Volume 126 (2000), pp. 106-130 | DOI | MR | Zbl
[8] Estimating the Held-Karp lower bound for the geometric TSP, Eur. J. Oper. Res., Volume 102 (1997), pp. 157-175 | DOI | Zbl
[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 | DOI | MR | Zbl
[10] Analysis of the Held-Karp lower bound for the asymmetric TSP, Oper. Res. Lett., Volume 12 (1992), pp. 83-88 | DOI | MR | Zbl
Cited by Sources: