Efficient optimization of the Held–Karp lower bound
Open Journal of Mathematical Optimization · 2021
DOI: 10.5802/ojmo.11 ↗Kurz gefasst
Fachartikel in der Zeitschrift Open Journal of Mathematical Optimization, 2021. Verfasst von Giovanni Righini. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 10 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
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