Approximate solutions to the Travelling Salesperson Problem on semimetric graphs
M Krukowski, F Turoboś - arXiv preprint arXiv:2105.07275, 2021 - arxiv.org
arXiv preprint arXiv:2105.07275, 2021•arxiv.org
With the aid of the relaxed polygonal inequality (introduced by Fagin et al.) we strive to
extend the applicability of Christofides approximation technique to the scope of all complete
finite weighted graphs with positive weights. First section acquaints the Reader with the
class of semimetric graphs and proves that every finite graph admits $\gamma $-polygon
structure. Sections 2 and 3 establish the necessary notions from the graph and optimization
theory to tackle the Traveling Salesperson Problem. In section 4 the minimal spanning tree …
extend the applicability of Christofides approximation technique to the scope of all complete
finite weighted graphs with positive weights. First section acquaints the Reader with the
class of semimetric graphs and proves that every finite graph admits $\gamma $-polygon
structure. Sections 2 and 3 establish the necessary notions from the graph and optimization
theory to tackle the Traveling Salesperson Problem. In section 4 the minimal spanning tree …
With the aid of the relaxed polygonal inequality (introduced by Fagin et al.) we strive to extend the applicability of Christofides approximation technique to the scope of all complete finite weighted graphs with positive weights. First section acquaints the Reader with the class of semimetric graphs and proves that every finite graph admits -polygon structure. Sections 2 and 3 establish the necessary notions from the graph and optimization theory to tackle the Traveling Salesperson Problem. In section 4 the minimal spanning tree method is introduced, while section 5 focuses on the analysis of this method through the lens of -polygon graphs. The final section of the paper adjusts the technique of Christofides by obtaining approximation for the TSP.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果