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.APPROX-RANDOM.2016.16
URN: urn:nbn:de:0030-drops-66391
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6639/
Go to the corresponding LIPIcs Volume Portal

Marx, Dániel ; Salmasi, Ario ; Sidiropoulos, Anastasios

Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs

pdf-format:
LIPIcs-APPROX-RANDOM-2016-16.pdf (1 MB)

Abstract

In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability of ATSP on topologically restricted graphs. It has been shown by Oveis Gharan and Saberi [SODA, 2011] that there exists polynomial-time constant-factor approximations on planar graphs and more generally graphs of constant orientable genus. This result was extended to non-orientable genus by Erickson and Sidiropoulos [SoCG, 2014].

We show that for any class of nearly-embeddable graphs, ATSP admits a polynomial-time constant-factor approximation. More precisely, we show that for any fixed non-negative k, there exist positive alpha and beta, such that ATSP on n-vertex k-nearly-embeddable graphs admits an alpha-approximation in time O(n^beta). The class of k-nearly-embeddable graphs contains graphs with at most k apices, k vortices of width at most k, and an underlying surface of either orientable or non-orientable genus at most k. Prior to our work, even the case of graphs with a single apex was open. Our algorithm combines tools from rounding the Held-Karp LP via thin trees with dynamic programming.

We complement our upper bounds by showing that solving ATSP exactly on graphs of pathwidth k (and hence on k-nearly embeddable graphs) requires time n^{Omega(k)}, assuming the Exponential-Time Hypothesis (ETH). This is surprising in light of the fact that both TSP on undirected graphs and Minimum Cost Hamiltonian Cycle on directed graphs are FPT parameterized by treewidth.

BibTeX - Entry

@InProceedings{marx_et_al:LIPIcs:2016:6639,
  author =	{D{\'a}niel Marx and Ario Salmasi and Anastasios Sidiropoulos},
  title =	{{Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{16:1--16:54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6639},
  URN =		{urn:nbn:de:0030-drops-66391},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.16},
  annote =	{Keywords: asymmetric TSP, approximation algorithms, nearly-embeddable graphs, Held-Karp LP, exponential time hypothesis}
}

Keywords: asymmetric TSP, approximation algorithms, nearly-embeddable graphs, Held-Karp LP, exponential time hypothesis
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

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