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

3 papers · 1 filter

cs.DS2020★ 1 cited

Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches

Federica Cecchetto, Vera Traub, Rico Zenklusen

We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by on…

cs.DS2020

Improving the Approximation Ratio for Capacitated Vehicle Routing

Jannis Blauth, Vera Traub, Jens Vygen

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for th…

cs.DM2020

Improving on Best-of-Many-Christofides for $T$ -tours

Vera Traub

The $T$ -tour problem is a natural generalization of TSP and Path TSP. Given a graph $G = (V, E)$ , edge cost $c : E \to R_{\geq 0}$ , and an even cardinality set $T \subseteq V$ ,…

Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches

Improving the Approximation Ratio for Capacitated Vehicle Routing

Improving on Best-of-Many-Christofides for T-tours

Improving on Best-of-Many-Christofides for $T$ -tours