Vera Traub



This website will not be updated anymore from September 2022.



Publications and Preprints

  • Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
    with J. Blauth, S. Held, D. Müller, N. Schlomberg, T. Tröbst, and J. Vygen.

  • Better-Than-4/3-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation
    with F. Cecchetto and R. Zenklusen.

  • Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
    with F. Grandoni and A. Jabal Ameli.
    STOC 2022, to appear. [arXiv]

  • Local Search for Weighted Tree Augmentation and Steiner Tree
    with R. Zenklusen.
    SODA 2022. [arXiv]

  • A Better-Than-2 Approximation for Weighted Tree Augmentation
    with R. Zenklusen.
    FOCS 2021. [arXiv]

  • Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
    with F. Cecchetto and R. Zenklusen.
    STOC 2021. [arXiv]

  • Improving the Approximation Ratio for Capacitated Vehicle Routing
    with J. Blauth and J. Vygen.
    IPCO 2021. (best paper award)

  • Improving on Best-Of-Many-Christofides for T-tours
    Operation Research Letters, 2020. [arXiv]

  • An Improved Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    with J. Vygen.
    SIAM Journal on Computing, 2022. Extended abstract: STOC 2020. [arXiv]

  • Reducing Path TSP to TSP
    with J. Vygen and R. Zenklusen.
    SIAM Journal on Computing, to appear. Extended abstract: STOC 2020. [arXiv]

  • A fast (2+2/7)-approximation algorithm for capacitated cycle covering
    with T. Tröbst.
    Mathematical Programming, 2022. Extended abstract: IPCO 2020.

  • The asymmetric traveling salesman path LP has constant integrality ratio
    with A. Köhne and J. Vygen.
    Mathematical Programming, 2020. Extended abstract: IPCO 2019. [arXiv]

  • An improved upper bound on the integrality ratio for the s-t-path TSP
    with J. Vygen.
    Operations Research Letters, 2019. [arXiv]

  • Beating the integrality ratio for s-t-tours in graphs
    with J. Vygen.
    SIAM Journal on Computing, 2020. Extended abstract: FOCS 2018. [arXiv]

  • Approaching 3/2 for the s-t-path TSP
    with J. Vygen.
    Journal of the ACM, 2019. Extended abstract: SODA 2018. (best paper award)

  • Layers and Matroids for the Traveling Salesman's Paths
    with F. Schalekamp, A. Sebő, and A. van Zuylen.
    Operations Research Letters, 2018. [arXiv]

  • Global Routing with Timing Constraints
    with S. Held, D. Müller, D. Rotter, R. Scheifele, and J. Vygen.
    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018. Extended abstract: ICCAD 2015.



My PhD thesis is available here.
It has been awarded the EATCS Distinguished Dissertation Award and the Hausdorff Memorial Prize.