Efficient optimization of the Held–Karp lower bound
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.
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}
}
EUVIMED