BARC Talk by Vera Traub

On Friday October 26, Vera Traub, PhD student at the University of Bonn, will give a talk in BARC "Beating the integrality ratio for s-t-tours in graphs".

Titel

Beating the integrality ratio for s-t-tours in graphs

Abstract

Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this work, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497.

Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebő and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).

This is joint work with Jens Vygen.

Bio

Vera Traub is a PhD student at the University of Bonn, where she also obtained her Masters degree in Mathematics in 2017. In 2018 she received a SODA best-paper award. Her research interests include combinatorial optimization and approximation algorithms. One focus of her current research is the traveling salesman problem.