We are excited to announce a new online seminar - IGAFIT Algorithmic Colloquium. This new event aims to integrate the European algorithmic community and keep it connected during the times of the pandemic. This online seminar will take place biweekly on Thursday at 14:00 CET, with the talks lasting for 45 minutes. Each talk will be followed by a networking and discussion session on topics related to the talk. We cordially invite all participants to this session. The meeting will be run on Airmeet. More details on the event can be found on IGAFIT web page.
The first talk will be held on the 1st of October 2020.
October 1, 2020
Vera Traub, University of Bonn
Title: An improved approximation algorithm for ATSP
Abstract: In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). In this work we revisit their algorithm. While following their overall framework, we improve on each part of it.
Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio.
Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22.
This is joint work with Jens Vygen.
Other upcoming talks include:
October 15, 2020
Thatchaphol Saranurak, Toyota Technological Institute at Chicago
Title: An almost-linear time deterministic algorithm for expander decomposition
October 29, 2020
Nathan Klein, University of Bonn
Title: A (Slightly) Improved Approximation Algorithm for Metric TSP
For more details please contact the Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Adi Rosén
Eva Rotenberg
Piotr Sankowski
Christian Sohler