License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.3
URN: urn:nbn:de:0030-drops-99024
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9902/
Go to the corresponding LIPIcs Volume Portal

Svensson, Ola

Algorithms for the Asymmetric Traveling Salesman Problem (Invited Paper)

pdf-format:
LIPIcs-FSTTCS-2018-3.pdf (0.2 MB)

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 constant-factor 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 constant-factor 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 constant-factor 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:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9902},
  URN =		{urn:nbn:de:0030-drops-99024},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI