Abstract
The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum total distance that visits each city once. In spite of significant research efforts, current techniques seem insufficient for settling the approximability of the traveling salesman problem. The gap in our understanding is especially large in the general asymmetric setting where the distance from city i to j is not assumed to equal the distance from j to i.
Indeed, until recently, it remained an open problem to design an algorithm with any constant approximation guarantee. This status is particularly intriguing as the standard linear programming relaxation is believed to give a constantfactor approximation algorithm, where the constant may in fact be as small as 2.
In this talk, we will give an overview of old and new approaches for settling this question. We shall, in particular, talk about our new approach that gives the first constantfactor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. The main idea of our approach is to first give a generic reduction to structured instances and on those instances we then solve an easier problem (but equivalent in terms of constantfactor approximation) obtained by relaxing the general connectivity requirements into local connectivity conditions.
This is based on joint work with Jakub Tarnawski and László A. Végh.
BibTeX  Entry
@InProceedings{svensson:LIPIcs:2018:9902,
author = {Ola Svensson},
title = {{Algorithms for the Asymmetric Traveling Salesman Problem (Invited Paper)}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {3:13:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770934},
ISSN = {18688969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9902},
URN = {urn:nbn:de:0030drops99024},
doi = {10.4230/LIPIcs.FSTTCS.2018.3},
annote = {Keywords: Approximation algorithms, combinatorial optimization, linear programming, traveling salesman problem}
}
Keywords: 

Approximation algorithms, combinatorial optimization, linear programming, traveling salesman problem 
Collection: 

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) 
Issue Date: 

2018 
Date of publication: 

05.12.2018 