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 2019Show all

2 papers · 1 filter

cs.DM2019

An improved approximation algorithm for ATSP

Vera Traub, Jens Vygen

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Végh. We improve on each part of this algorithm. We…

cs.DM2019

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…