Document Open Access Logo

Fine-Grained Complexity Analysis of Two Classic TSP Variants

Authors Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard Woeginger

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.5.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Mark de Berg
Kevin Buchin
Bart M. P. Jansen
Gerhard Woeginger

Cite As Get BibTex

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard Woeginger. Fine-Grained Complexity Analysis of Two Classic TSP Variants. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.5

Abstract

We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity.

Our first set of results is motivated by the Bitonic tsp problem: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamicprogramming exercise to solve this problem in O(n^2) time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Fréchet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic tsp in O(n*log^2(n)) time and its bottleneck version in O(n*log^3(n)) time. In the more general pyramidal tsp problem, the points to be visited are labeled 1, ..., n and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) tsp problem also work for the pyramidal tsp problem in the plane.

Our second set of results concerns the popular k-opt heuristic for tsp in the graph setting. More precisely, we study the k-opt decision problem, which asks whether a given tour can be improved by a k-opt move that replaces k edges in the tour by k new edges. A simple algorithm solves k-opt in O(n^k) time for fixed k. For 2-opt, this is easily seen to be optimal. For k = 3 we prove that an algorithm with a runtime of the form ~O(n^{3-epsilon}) exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. For general k-opt, it is known that a runtime of f(k)*n^{o(k/log(k))} would contradict the Exponential Time Hypothesis. The results for k = 2, 3 may suggest that the actual time complexity of k-opt is Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best k-move in O(n^{lfoor 2k/3 rfloor +1}) time for fixed k >= 3. This implies that 4-opt can be solved in O(n^3) time, matching the best-known algorithm for 3-opt. Finally, we show how to beat the quadratic barrier for k = 2 in two important settings, namely for points in the plane and when we want to solve 2-opt repeatedly

Subject Classification

Keywords
  • Traveling salesman problem
  • fine-grained complexity
  • bitonic tours
  • k-opt

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th FOCS, pages 59-78, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.14.
  2. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska-Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proc. 26th SODA, pages 1681-1697, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.112.
  3. Amir Abboud, Virginia Vassilevska-Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proc. 47th STOC, pages 41-50, 2015. URL: http://dx.doi.org/10.1145/2746539.2746594.
  4. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci., 54(2):255-262, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1388.
  5. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. 47th STOC, pages 51-58, 2015. URL: http://dx.doi.org/10.1145/2746539.2746612.
  6. Md. Fazle Baki and Santosh N. Kabadi. Pyramidal traveling salesman problem. Computers & OR, 26(4):353-369, 1999. URL: http://dx.doi.org/10.1016/S0305-0548(98)00067-7.
  7. Jon Louis Bentley. Experiments on traveling salesman heuristics. In Proc. 1st SODA, pages 91-99, 1990. Google Scholar
  8. J.L. Bently and J.B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms, 1:301-358, 1980. URL: http://dx.doi.org/10.1016/0196-6774(80)90015-2.
  9. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th FOCS, pages 661-670, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.76.
  10. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Venkatesan Guruswami, editor, Proc. 56th FOCS, pages 79-97. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.15.
  11. Rainer E. Burkard, Vladimir G. Deineko, René van Dal, Jack A. A. van der Veen, and Gerhard J. Woeginger. Well-solvable special cases of the traveling salesman problem: A survey. SIAM Review, 40(3):496-546, 1998. URL: http://dx.doi.org/10.1137/S0036144596297514.
  12. J. Carlier and P. Villon. A new heuristic for the travelling salesman problem. RAIRO - Operations Research, 24:245-253, 1990. Google Scholar
  13. Barun Chandra, Howard J. Karloff, and Craig A. Tovey. New results on the old k-OPT algorithm for the traveling salesman problem. SIAM J. Comput., 28(6):1998-2029, 1999. URL: http://dx.doi.org/10.1137/S0097539793251244.
  14. M. Chrobak, T. Szymacha, and A. Krawczyk. A data structure useful for finding hamiltonian cycles. Theoretical Computer Science, 71(3):419-424, 1990. URL: http://dx.doi.org/10.1016/0304-3975(90)90053-K.
  15. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  16. G. A. Croes. A method for solving traveling-salesman problems. Operations Research, 6:791-812, 1958. URL: http://dx.doi.org/10.1287/opre.6.6.791.
  17. Matthias Englert, Heiko Röglin, and Berthold Vöcking. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68(1):190-264, 2014. URL: http://dx.doi.org/10.1007/s00453-013-9801-4.
  18. Steven Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987. URL: http://dx.doi.org/10.1007/BF01840357.
  19. Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, and G. Ostheimer. Data structures for traveling salesmen. J. Algorithms, 18(3):432-479, 1995. URL: http://dx.doi.org/10.1006/jagm.1995.1018.
  20. P.C. Gilmore, E.L. Lawler, and D.B. Shmoys. Well-solved special cases. In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, editors, The Traveling Salesman Problem, pages 87-143. Wiley, New York, 1985. Google Scholar
  21. Fred Glover. Finding a best traveling salesman 4-Opt move in the same time as a best 2-Opt move. J. Heuristics, 2(2):169-179, 1996. URL: http://dx.doi.org/10.1007/BF00247211.
  22. Jiong Guo, Sepp Hartung, Rolf Niedermeier, and Ondrej Suchý. The parameterized complexity of local search for TSP, more refined. Algorithmica, 67(1):89-110, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9685-8.
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  24. D. S. Johnson and L. A. McGeoch. Experimental analysis of heuristics for the STSP. In G. Gutin and A. Punnen, editors, The Traveling Salesman Problem and its Variations, pages 369-443. Kluwer Academic Publishers, Dordrecht, 2002. Google Scholar
  25. D.S. Johnson and L.A McGeoch. The traveling salesman problem: A case study in local optimization. In E Aarts and J.K. Lenstra, editors, Local search in combinatorial optimization, pages 215-310. Wiley, Chichester, 1997. Google Scholar
  26. Marvin Künnemann and Bodo Manthey. Towards understanding the smoothed approximation ratio of the 2-opt heuristic. In Proc. 42nd ICALP, pages 859-871, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_70.
  27. Shen Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10):2245-2269, 1965. URL: http://dx.doi.org/10.1002/j.1538-7305.1965.tb04146.x.
  28. Dániel Marx. Searching the k-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett., 36(1):31-36, 2008. URL: http://dx.doi.org/10.1016/j.orl.2007.02.008.
  29. Ioannis Mavroidis, Ioannis Papaefstathiou, and Dionisios N. Pnevmatikatos. A fast FPGA-based 2-opt solver for small-scale euclidean traveling salesman problem. In IEEE Symposium on Field-Programmable Custom Computing Machines, pages 13-22, 2007. URL: http://dx.doi.org/10.1109/FCCM.2007.40.
  30. Molly A. O'Neil and Martin Burtscher. Rethinking the parallelization of random-restart hill climbing: a case study in optimizing a 2-opt TSP solver for GPU execution. In Proceedings of the 8th Workshop on General Purpose Processing using GPUs, pages 99-108, 2015. URL: http://dx.doi.org/10.1145/2716282.2716287.
  31. Liam Roditty and Virginia Vassilevska-Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In Proc. 52nd FOCS, pages 180-189, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.27.
  32. Jack Snoeyink. Point location. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry (2nd ed.). CRC Press, 2004. Google Scholar
  33. Virginia Vassilevska-Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. 51th FOCS, pages 645-654, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  34. Andrew Chi-Chih Yao. Lower bounds for algebraic computation trees with integer inputs. SIAM J. Comput., 20(4):655-668, 1991. URL: http://dx.doi.org/10.1137/0220041.
  35. Gideon Yuval. An algorithm for finding all shortest paths using n^2.81 infinite-precision multiplications. Inf. Process. Lett., 4(6):155-156, 1976. URL: http://dx.doi.org/10.1016/0020-0190(76)90085-5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact