EUVIMEDEUVIMED entdecken
Crossref

Efficient optimization of the Held–Karp lower bound

Giovanni Righini

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →