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

Jens Vygen; Vera Traub

arxiv: 1808.10734 · v2 · pith:RVZRBJ7Bnew · submitted 2018-08-31 · 💻 cs.DM · cs.DS· math.CO

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

Vera Traub , Jens Vygen This is my paper

classification 💻 cs.DM cs.DSmath.CO

keywords improvedboundintegralitypathratioupperalgorithmanalysis

0 comments

read the original abstract

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

This paper has not been read by Pith yet.

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

discussion (0)