Open Journal of Mathematical Optimization

Efficient optimization of the Held–Karp lower bound
Giovanni Righini1
1 University of Milan, Department of Computer Science via Celoria 18, Milano Italy
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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.11
Keywords: Traveling salesman problem, Minimum spanning tree, Held–Karp lower bound, Union-Find data-structure.
Giovanni Righini 1

1 University of Milan, Department of Computer Science via Celoria 18, Milano Italy
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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  - 
%0 Journal Article
%A Giovanni Righini
%T Efficient optimization of the Held–Karp lower bound
%J Open Journal of Mathematical Optimization
%D 2021
%P 1-17
%V 2
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.11/
%R 10.5802/ojmo.11
%G en
%F OJMO_2021__2__A9_0
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

[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 | DOI | Zbl

[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 | Zbl

[4] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein 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] Michael Held; Richard M. Karp The Traveling-Salesman Problem and Minimum Spanning Trees, Oper. Res., Volume 18 (1970), pp. 1138-1162 | DOI | MR | Zbl

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

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

[10] David P. Williamson 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: