paper

An improved upper bound on the integrality ratio for the --path TSP

arXiv:1808.10734

Abstract

We give an improved analysis of the best-of-many Christofides algorithm with lonely edge deletion, which was proposed by Sebő and van Zuylen [2016]. This implies an improved upper bound on the integrality ratio of the standard LP relaxation for the --path TSP.

An improved upper bound on the integrality ratio for the $s$-$t$-path TSP · wovepaper