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