Editing Travelling salesman problem (section)

==Computational complexity==
The problem has been shown to be [[NP-hard]] (more precisely, it is complete for the [[complexity class]] FP<sup>NP</sup>; see [[function problem]]), and the [[decision problem]] version ("given the costs and a number ''x'', decide whether there is a round-trip route cheaper than ''x''") is [[NP-complete]]. The [[Bottleneck traveling salesman problem|bottleneck travelling salesman problem]] is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with [[Euclidean distance]]s, as well as in a number of other restrictive cases. Removing the condition of visiting each city "only once" does not remove the NP-hardness, since in the planar case there is an optimal tour that visits each city only once (otherwise, by the [[triangle inequality]], a shortcut that skips a repeated visit would not increase the tour length).

===Complexity of approximation===

In the general case, finding a shortest travelling salesman tour is [[Combinatorial optimization#NP optimization problem|NPO]]-complete.<ref>{{cite report |last1=Orponen|first1=P. |last2=Mannila |first2=H. |author2-link=Heikki Mannila |year=1987 |title=On approximation preserving reductions: Complete problems and robust measures' |id= Technical Report C-1987–28 |publisher=Department of Computer Science, University of Helsinki}}</ref> If the distance measure is a [[metric (mathematics)|metric]] (and thus symmetric), the problem becomes [[APX]]-complete,{{sfnp|Papadimitriou|Yannakakis|1993}} and [[Christofides algorithm|the algorithm of Christofides and Serdyukov]] approximates it within 1.5.{{sfnp|Christofides|1976}}<ref>{{citation |last=Serdyukov |first=Anatoliy I.|date=1978|title=О некоторых экстремальных обходах в графах |trans-title =On some extremal walks in graphs |language=ru |journal=Upravlyaemye Sistemy |volume=17 |pages=76–79 |url=http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf}}</ref><ref name="bs20" />

If the distances are restricted to 1 and 2 (but still are a metric), then the approximation ratio becomes 8/7.{{sfnp|Berman|Karpinski|2006}} In the asymmetric case with [[triangle inequality]], in 2018, a constant factor approximation was developed by Svensson, Tarnawski, and Végh.<ref>{{Cite book |last1=Svensson|first1=Ola |last2=Tarnawski|first2=Jakub|last3=Végh|first3=László A.|title=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |chapter=A constant-factor approximation algorithm for the asymmetric traveling salesman problem |date=2018 |chapter-url=http://eprints.lse.ac.uk/106582/1/ATSP.pdf |series=Stoc 2018 |language=en|location=Los Angeles, CA, USA|publisher=ACM Press|pages=204–213|doi=10.1145/3188745.3188824|isbn=978-1-4503-5559-9 |s2cid=12391033 }}</ref> An algorithm by [[Vera Traub]] and {{ill|Jens Vygen|de}} achieves a performance ratio of <math>22+\varepsilon</math>.<ref>{{Cite book |last1=Traub|first1=Vera|author1-link=Vera Traub|last2=Vygen|first2=Jens|title=Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing |chapter=An improved approximation algorithm for ATSP |date=2020-06-08|chapter-url=https://dl.acm.org/doi/10.1145/3357713.3384233|series=Stoc 2020|location=Chicago, IL|publisher=ACM|pages=1–13 |doi=10.1145/3357713.3384233|isbn=978-1-4503-6979-4|arxiv=1912.00670|s2cid=208527125}}</ref> The best known inapproximability bound is 75/74.{{sfnp|Karpinski|Lampis|Schmied|2015}}

The corresponding maximization problem of finding the ''longest'' travelling salesman tour is approximable within 63/38.{{sfnp|Kosaraju|Park|Stein|1994}} If the distance function is symmetric, then the longest tour can be approximated within 4/3 by a deterministic algorithm{{sfnp|Serdyukov|1984}} and within <math>(33+\varepsilon)/25</math> by a randomized algorithm.{{sfnp|Hassin|Rubinstein|2000}}