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 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. |
||
| Date: | Thursday, October 15, 2020 | ||
| Title: | An almost-linear 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 almost-linear 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 n0.4999 worst-case update time by giving an algorithm with no(1) worst-case update time. The result also implies almost-linear-time 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. | ||