Efficient optimization of the Held–Karp lower bound
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 $\bar{p} \in V$, by computing a minimum cost tree spanning $V \backslash \lbrace \bar{p}\rbrace $ and adding two minimum cost edges adjacent to...
Main Author: | Righini, Giovanni |
---|---|
Format: | Article |
Language: | English |
Published: |
Université de Montpellier
2021-11-01
|
Series: | Open Journal of Mathematical Optimization |
Subjects: | |
Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.11/ |
Similar Items
-
BASIS PATH TESTING OF ITERATIVE DEEPENING SEARCH AND HELD-KARP ON PATHFINDING ALGORITHM
by: I Gede Surya Rahayuda, et al.
Published: (2017-12-01) -
Converting MST to TSP Path by Branch Elimination
by: Pasi Fränti, et al.
Published: (2020-12-01) -
经典组合优化问题的概率极限定理(Probability limit theorems of classical combinatorial optimization problems)
by: SUZhong-gen(苏中根)
Published: (2000-11-01) -
Optimalisasi Rute Distribusi Kurir Menggunakan Metode Traveling Salesman Problem (Studi Kasus: JNE Balige)
by: Devis Wawan Saputra
Published: (2022-08-01) -
Simulated Annealing Algorithm for Determining Travelling Salesman Problem Solution and Its Comparison with Branch and Bound Method
by: Bib Paruhum Silalahi, et al.
Published: (2022-07-01)