The IGAFIT Algorithmic Colloquia are organized biweekly on Thursdays at 14:00 CET. After the talk we will have an online networking/discussion session for approximately 1 hour. Both of these events will be run through the Airmeet platform. The first seminar will take place on October 1, 2020.
The schedule of upcoming events is as follows.
Date:  Thursday, October 1, 2020  Airmeet link 

Title:  An improved approximation algorithm for ATSP 

Speaker:  Vera Traub, University of Bonn 

Abstract:  In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constantfactor 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. 
Date:  Thursday, October 15, 2020  
Title:  An almostlinear time deterministic algorithm for expander decomposition  
Speaker:  Thatchaphol Saranurak, Toyota Technological Institute at Chicago  
Abstract:  Expander decomposition is a powerful tool in many areas on graph algorithms (e.g. approximation algorithm, dynamic algorithm, distributed algorithm, property testing, and sketching). We give a deterministic algorithm for finding this decomposition in almostlinear time. Previous algorithms are either randomized or take quadratic time. As a consequence, we resolve a major open problem if there is a deterministic dynamic connectivity algorithm with n^{0.4999} worstcase update time by giving an algorithm with n^{o(1)} worstcase update time. The result also implies almostlineartime deterministic algorithms for approximate max flow, electric flow, and Laplacian solvers. Joint work with Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, and Richard Peng. 
Date:  Thursday, October 29, 2020  
Title:  A (Slightly) Improved Approximation Algorithm for Metric TSP  
Speaker:  Nathan Klein, University of Washington  
Abstract:  In this talk, I will describe recent work in which we obtain a 3/2ε approximation algorithm for metric TSP, for some ε>10^{36}. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978]. The talk will focus on giving an overview of the key ideas involved. This is joint work with Anna Karlin and Shayan Oveis Gharan. 