4 papers · 1 filter
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, Rico Zenklusen
We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an -a…
The asymmetric traveling salesman path LP has constant integrality ratio
Anna Köhne, Vera Traub, Jens Vygen
We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If and denot…
An improved upper bound on the integrality ratio for the --path TSP
Vera Traub, Jens Vygen
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…
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich +3
In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph , edge costs , terminal pairs , and…