Efficient optimization of the Held–Karp lower bound

Righini, Giovanni

Open Journal of Mathematical Optimization, Tome 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 $\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.

Mots clés : Traveling salesman problem, Minimum spanning tree, Held–Karp lower bound, Union-Find data-structure.

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

[2] Benchimol, Pascal; Régin, Jean-Charles; Rousseau, Louis-Martin; Rueher, Michel; van Hoeve, Willem-Jan 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] Chekuri, Chandra; Quanrud, Kent 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] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introduction to Algorithms, MIT Press, 2009 | Zbl

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

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

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

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

[9] Volgenant, Ton; Jonker, Roy 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] Williamson, David P. Analysis of the Held-Karp lower bound for the asymmetric TSP, Oper. Res. Lett., Volume 12 (1992), pp. 83-88 | DOI | MR | Zbl