EUVIMEDObjevte EUVIMED
Crossref

Efficient optimization of the Held–Karp lower bound

Giovanni Righini

Open Journal of Mathematical Optimization · 2021

DOI: 10.5802/ojmo.11 ↗

At a glance

Journal article in Open Journal of Mathematical Optimization, 2021. Written by Giovanni Righini. Cited 2 times so far (Crossref); 10 references.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

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.

Cite

APA

Righini, G. (2021). Efficient optimization of the Held–Karp lower bound. Open Journal of Mathematical Optimization. https://doi.org/10.5802/ojmo.11

Vancouver

Righini G. Efficient optimization of the Held–Karp lower bound. Open Journal of Mathematical Optimization. 2021. doi:10.5802/ojmo.11

BibTeX
@article{Righini2021,
  author = {Righini, Giovanni},
  title = {Efficient optimization of the Held–Karp lower bound},
  journal = {Open Journal of Mathematical Optimization},
  year = {2021},
  doi = {10.5802/ojmo.11}
}
Start for free →