Vera Traub

I am a professor at the Research Institute for Discrete Mathematics at the University of Bonn and a member of the Hausdorff Center for Mathematics.

My research interests are mostly in the areas of combinatorial optimization and approximation algorithms. Some specific topics I have worked on recently are the traveling salesman problem, vehicle routing, connectivity augmentation, and Steiner trees.

I obtained my PhD in 2020 from the University of Bonn, where my advisor was Jens Vygen. Afterwards I spent two years as a postdoc in the group of Rico Zenklusen at ETH Zurich.
For my PhD thesis I received the Richard-Rado Prize, the EATCS Distinguished Dissertation Award, and the Hausdorff Memorial Prize. Recently, I received a Maryam Mirzakhani New Frontiers Prize and a Heinz Maier-Leibnitz Prize.

I am an Associate Editor of the journal Mathematics of Operations Research and I am/was a member of the following program committees:
SODA 2025, FOCS 2024, ESA 2023, ICALP 2023, HALG 2023, SODA 2023, FOCS 2022, APPROX 2022, IPCO 2022, WAOA 2021, ESA 2020.

Book

Further Publications and Preprints

• The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2.
  with J. Byrka and F. Grandoni.
  FOCS 2024. [arXiv]
• Cost Allocation for Set Covering: the Happy Nucleolus
  with J. Blauth, A. Ellerbrock, and J. Vygen.
  [arXiv]
• Single-Source Unsplittable Flows in Planar Graphs
  with L. Vargas Koch and R. Zenklusen.
  SODA 2024. [arXiv]
• A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
  with R. Zenklusen.
  STOC 2023. [arXiv]
• 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.
  [arXiv]
• Better-Than-4/3-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation
  with F. Cecchetto and R. Zenklusen.
  Mathematical Programming, 2023. [arXiv]
• Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
  with F. Grandoni and A. Jabal Ameli.
  STOC 2022. [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.
  SIAM Journal on Computing, to appear. Extended abstract: STOC 2021. [arXiv]
• Improving the Approximation Ratio for Capacitated Vehicle Routing
  with J. Blauth and J. Vygen.
  Mathematical Programming, to appear. Extended abstract: IPCO 2021. (best paper award) [arXiv]
• 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, 2022. 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) [arXiv]
• 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.