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 2 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.

Efficient optimization of the Held–Karp lower bound / G. Righini. - In: OPEN JOURNAL OF MATHEMATICAL OPTIMIZATION.. - ISSN 2777-5860. - 2:(2021), pp. 9.1-9.17. [10.5802/ojmo.11]

Efficient optimization of the Held–Karp lower bound

G. Righini
2021

Abstract

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 2 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.
traveling salesman problem; minimum spanning tree; Held–Karp lower bound; union-find data-structure;
Settore MAT/09 - Ricerca Operativa
2021
3-nov-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
51 - OJMO - HK LB.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 634.29 kB
Formato Adobe PDF
634.29 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/903300
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact