showed an upper bound of . Lower bound By observing that is greater than times the distance between and the closest point , one gets (after a short computation) A better lower bound is obtained by observing that is greater than times the sum of the distances between and the closest and second closest points , which gives The currently best lower bound is Held and Karp gave a polynomial-time algorithm that provides numerical lower bounds for , and thus for which seem to be good up to more or less 1%. In particular, David S. Johnson obtained a lower bound by computer experiment: where 0.522 comes from the points near square boundary which have fewer neighbours, and Christine L. Valenzuela and Antonia J. Jones obtained the following other numerical lower bound: . Computational complexity The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; 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 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 distances, 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 NPO-complete. If the distance measure is a metric (and thus symmetric), the problem becomes APX-complete and the algorithm of Christofides and Serdyukov approximates it within 1.5. If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 8/7. In the asymmetric case with triangle inequality, up until recently only logarithmic performance guarantees were known. In 2018, a constant factor approximation was developed by Svensson, Tarnawski and Végh. The best current algorithm, by Traub and Vygen, achieves performance ratio of . The best known inapproximability bound is 75/74. The corresponding maximization problem of finding the longest travelling salesman tour is approximable within 63/38. If the distance function is symmetric, the longest tour can be approximated within