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
<https://www.airmeet.com/e/55923fa0-eee9-11ea-8530-b3eab1e75816>. More
details on the event can be found on IGAFIT web page
<http://igafit.mimuw.edu.pl/?page_id=483786>.
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
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
