Showing 2018Show all
3 papers · 1 filter
cs.DM2018
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…
cs.DM2018
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…
cs.DS2018
Vehicle Routing with Subtours
Stephan Held, Jochen Könemann, Jens Vygen
When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items a…