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.ESA.2017.30
URN: urn:nbn:de:0030-drops-78539
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7853/
Go to the corresponding LIPIcs Volume Portal

Cygan, Marek ; Kowalik, Lukasz ; Socala, Arkadiusz

Improving TSP Tours Using Dynamic Programming over Tree Decompositions

pdf-format:
LIPIcs-ESA-2017-30.pdf (0.6 MB)

Abstract

Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation which removes k edges from H, and adds k edges of G so that a new tour H' is formed. The popular k-opt heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves.

Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(n^k). At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an O(n^{floor(2/3k)+1})-time algorithm.

We show an algorithm which runs in O(n^{(1/4 + epsilon_k)k}) time, where lim_{k -> infinity} epsilon_k = 0. It improves over the state of the art for every k >= 5. For the most practically relevant case k=5 we provide a slightly refined algorithm running in O(n^{3.4}) time. We also show that for the k=4 case, improving over the O(n^3)-time algorithm of de Berg et al. would be a major breakthrough: an O(n^{3 - epsilon})-time algorithm for any epsilon > 0 would imply an O(n^{3 - delta})-time algorithm for the All Pairs Shortest Paths problem, for some delta>0.

BibTeX - Entry

@InProceedings{cygan_et_al:LIPIcs:2017:7853,
  author =	{Marek Cygan and Lukasz Kowalik and Arkadiusz Socala},
  title =	{{Improving TSP Tours Using Dynamic Programming over Tree Decompositions}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7853},
  URN =		{urn:nbn:de:0030-drops-78539},
  doi =		{10.4230/LIPIcs.ESA.2017.30},
  annote =	{Keywords: TSP, treewidth, local search, XP algorithm, hardness in P}
}

Keywords: TSP, treewidth, local search, XP algorithm, hardness in P
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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