22 lutego 2016 10:00
Seminarium ZZOiAA: Jakub Tarnawski o "How to get constant-factor approximation for the Asymmetric Traveling Salesman Problem?"
Na seminarium ZZOiAA, które wyjątkowo odbędzie się w poniedziałek (22.02.16; początek równo o 10.00, więc zapraszamy na 9:55; sala 141) wystąpi gość z Lozanny Kuba Tarnawski.
Abstract
The Traveling Salesman Problem (TSP) - one of finding the shortest tour visiting all vertices of an edge-weighted graph - is the best-known problem in combinatorial optimization. We consider its asymmetric version, where the graph is directed. In contrast to the symmetric version, where a classical algorithm due to Christofides (1976) has an approximation ratio of 1.5, we do not know any constant-factor approximation for the asymmetric version (the state-of-the-art is O(log n / log log n) by Asadpour, Goemans, Mądry, Oveis Gharan and Saberi (2010)). Obtaining one is a notorious open problem.
In a recent major development, Svensson (FOCS 2015) gave a constant-factor approximation algorithm for the natural special case where the graph is unweighted. This result is obtained by a black-box reduction to an easier new problem called Local-Connectivity ATSP, which turns out to be simple to solve on unweighted graphs. Can we solve it for any graph?
I will discuss the problem and its standard linear programming relaxation, survey the previous algorithms and explain Svensson's reduction. I will also show how to solve the easier Local-Connectivity ATSP problem for unweighted graphs and, time permitting, on graphs with two different edge weights (Svensson, T., Vegh (IPCO 2016)).