Colloquium on "A (Slightly) Improved Approximation Algorithm for Metric
TSP" given by Nathan Klein, University of Washington. The seminar will take
place at 14:00 CEST (local time in central Europe), and will be followed by
a discussion session. We would like to invite you to take part in the event
including the networking session. This new event aims to integrate the
European algorithmic community and keep it connected during the times of
the pandemic. The meeting will be held using Airmeet platform and to attend
please go to https://www.airmeet.com/e/23023140-1508-11eb-b9e0-91ba5e70c4b8.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786 or Facebook
https://fb.me/e/cmlhdv2ZS.
We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.
The details of the talk are given below.
October 29, 2020, 14:00 CET
Nathan Klein, University of Washington
Title: A (Slightly) Improved Approximation Algorithm for Metric TSP
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.
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
