Vera Traub

activity

20172024

\frac{3}{2}

for the

s

t

-path TSP

3 citations · 10 across the 13 of their papers we have counts for

collaborators

Showing 2018Show all

2 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 $ρ_{ATSP}$ and $ρ_{ATSPP}$ denot…

cs.DM2018★ 1 cited

An improved upper bound on the integrality ratio for the $s$ - $t$ -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…

The asymmetric traveling salesman path LP has constant integrality ratio

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

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