7124:, examined spatial cognition in pigeons by studying their flight patterns between multiple feeders in a laboratory in relation to the travelling salesman problem. In the first experiment, pigeons were placed in the corner of a lab room and allowed to fly to nearby feeders containing peas. The researchers found that pigeons largely used proximity to determine which feeder they would select next. In the second experiment, the feeders were arranged in such a way that flying to the nearest feeder at every opportunity would be largely inefficient if the pigeons needed to visit every feeder. The results of the second experiment indicate that pigeons, while still favoring proximity-based solutions, "can plan several steps ahead along the route when the differences in travel costs between efficient and less efficient routes based on proximity become larger." These results are consistent with other experiments done with non-primates, which have proven that some non-primates were able to plan complex travel routes. This suggests non-primates may possess a relatively sophisticated spatial cognitive ability.
7107:. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient, for graphs with 10â20 nodes, to 11% less efficient for graphs with 120 nodes. The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic. However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to affect performance in the task. Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems, and have also led to new insights into the mechanisms of human thought. The first issue of the
4331:
283:
that, given a near-optimal solution, one may be able to find optimality or prove optimality by adding a small number of extra inequalities (cuts). They used this idea to solve their initial 49-city problem using a string model. They found they only needed 26 cuts to come to a solution for their 49 city problem. While this paper did not give an algorithmic approach to TSP problems, the ideas that lay within it were indispensable to later creating exact solution methods for the TSP, though it would take 15 years to find an algorithmic approach in creating these cuts. As well as cutting plane methods, Dantzig, Fulkerson, and
Johnson used
33:
7359:(weil diese Frage in der Praxis von jedem Postboten, ĂŒbrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, fĂŒr endlich viele Punkte, deren paarweise AbstĂ€nde bekannt sind, den kĂŒrzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natĂŒrlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrĂŒcken wĂŒrden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nĂ€chstgelegenen Punkt, dann zu dem diesem nĂ€chstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kĂŒrzesten Weg."
3983:
2765:
3826:
227:(since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.
188:
3351:
2245:
3818:
4607:
the actual
Euclidean metric, Euclidean TSP is known to be in the Counting Hierarchy, a subclass of PSPACE. With arbitrary real coordinates, Euclidean TSP cannot be in such classes, since there are uncountably many possible inputs. Despite these complications, Euclidean TSP is much easier than the general metric case for approximation. For example, the minimum spanning tree of the graph associated with an instance of the Euclidean TSP is a
2922:
4223:-opt methods are widely considered the most powerful heuristics for the problem, and are able to address special cases, such as the Hamilton Cycle Problem and other non-metric TSPs that other heuristics fail on. For many years, LinâKernighanâJohnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best-known solutions for all other TSPs on which the method had been tried.
4330:
2760:{\displaystyle {\begin{aligned}\min \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\colon &&\\x_{ij}\in {}&\{0,1\}&&i,j=1,\ldots ,n;\\\sum _{i=1,i\neq j}^{n}x_{ij}={}&1&&j=1,\ldots ,n;\\\sum _{j=1,j\neq i}^{n}x_{ij}={}&1&&i=1,\ldots ,n;\\u_{i}-u_{j}+1\leq {}&(n-1)(1-x_{ij})&&2\leq i\neq j\leq n;\\2\leq u_{i}\leq {}&n&&2\leq i\leq n.\end{aligned}}}
400:
321:, and other sciences. In the 1960s, however, a new approach was created that, instead of seeking optimal solutions, would produce a solution whose length is provably bounded by a multiple of the optimal length, and in doing so would create lower bounds for the problem; these lower bounds would then be used with branch-and-bound approaches. One method of doing this was to create a
3346:{\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&\sum _{i\in Q}{\sum _{j\neq i,j\in Q}{x_{ij}}}\leq |Q|-1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.\\\end{aligned}}}
4521:. The Manhattan metric corresponds to a machine that adjusts first one coordinate, and then the other, so the time to move to a new point is the sum of both movements. The maximum metric corresponds to a machine that adjusts both coordinates simultaneously, so the time to move to a new point is the slower of the two movements.
3671:. In May 2004, the travelling salesman problem of visiting all 24,978 towns in Sweden was solved: a tour of length approximately 72,500 kilometres was found, and it was proven that no shorter tour exists. In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using
4891:. (Alternatively, the ghost edges have weight 0, and weight w is added to all other edges.) The original 3Ă3 matrix shown above is visible in the bottom left and the transpose of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by â
4100:. While this is a small increase in size, the initial number of moves for small problems is 10 times as big for a random start compared to one made from a greedy heuristic. This is because such 2-opt heuristics exploit 'bad' parts of a solution such as crossings. These types of heuristics are often used within
302:. The BeardwoodâHaltonâHammersley theorem provides a practical solution to the travelling salesman problem. The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.
4211:. The basic LinâKernighan technique gives results that are guaranteed to be at least 3-opt. The LinâKernighanâJohnson methods compute a LinâKernighan tour, and then perturb the tour by what has been described as a mutation that removes at least four edges and reconnects the tour in a different way, then
3736:
cities randomly distributed on a plane, the algorithm on average yields a path 25% longer than the shortest possible path; however, there exist many specially-arranged city distributions which make the NN algorithm give the worst route. This is true for both asymmetric and symmetric TSPs. Rosenkrantz
4606:
Like the general TSP, the exact
Euclidean TSP is NP-hard, but the issue with sums of radicals is an obstacle to proving that its decision version is in NP, and therefore NP-complete. A discretized version of the problem with distances rounded to integers is NP-complete. With rational coordinates and
4166:
in 1965. A special case of 3-opt is where the edges are not disjoint (two of the edges are adjacent to one another). In practice, it is often possible to achieve substantial improvement over 2-opt without the combinatorial cost of the general 3-opt by restricting the 3-changes to this special subset
3959:
Making a graph into an
Eulerian graph starts with the minimum spanning tree; all the vertices of odd order must then be made even, so a matching for the odd-degree vertices must be added, which increases the order of every odd-degree vertex by 1. This leaves us with a graph where every vertex is of
2770:
The first set of equalities requires that each city is arrived at from exactly one other city, and the second set of equalities requires that from each city there is a departure to exactly one other city. The last constraint enforces that there is only a single tour covering all cities, and not two
282:
method for its solution. They wrote what is considered the seminal paper on the subject in which, with these new methods, they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. Dantzig, Fulkerson, and
Johnson, however, speculated
4334:
1) An ant chooses a path among all possible paths and lays a pheromone trail on it. 2) All the ants are travelling on different paths, laying a trail of pheromones proportional to the quality of the solution. 3) Each edge of the best path is more reinforced than others. 4) Evaporation ensures that
3915:
To improve the lower bound, a better way of creating an
Eulerian graph is needed. By the triangle inequality, the best Eulerian graph must have the same cost as the best travelling salesman tour; hence, finding optimal Eulerian graphs is at least as hard as TSP. One way of doing this is by minimum
1212:
tour which visits all vertices, as the edges chosen could make up several tours, each visiting only a subset of the vertices; arguably, it is this global requirement that makes TSP a hard problem. The MTZ and DFJ formulations differ in how they express this final requirement as linear constraints.
4322:
ACS sends out a large number of virtual ant agents to explore many possible routes on the map. Each ant probabilistically chooses the next city to visit based on a heuristic combining the distance to the city and the amount of virtual pheromone deposited on the edge to the city. The ants explore,
557:
deals with a purchaser who is charged with purchasing a set of products. He can purchase these products in several cities, but at different prices, and not all cities offer the same products. The objective is to find a route between a subset of the cities that minimizes total cost (travel cost +
385:
that has been used in many recent record solutions. Gerhard
Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2006, Cook and others computed an optimal tour through an 85,900-city
336:
yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near-optimal solution method. However, this hope for improvement did not immediately materialize, and
Christofides-Serdyukov
3782:
for instances satisfying the triangle inequality. A variation of the NN algorithm, called nearest fragment (NF) operator, which connects a group (fragment) of nearest unvisited cities, can find shorter routes with successive iterations. The NF operator can also be applied on an initial solution
4198:
first published their method in 1972, and it was the most reliable heuristic for solving travelling salesman problems for nearly two decades. More advanced variable-opt methods were developed at Bell Labs in the late 1980s by David
Johnson and his research team. These methods (sometimes called
4524:
In its definition, the TSP does not allow cities to be visited twice, but many applications do not need this constraint. In such cases, a symmetric, non-metric instance can be reduced to a metric one. This replaces the original graph with a complete graph in which the inter-city distance
2867:
766:
4190:) of edges from the original tour, the variable-opt methods do not fix the size of the edge set to remove. Instead, they grow the set as the search process continues. The best-known method in this family is the LinâKernighan method (mentioned above as a misnomer for 2-opt).
6591:
571:. Several formulations are known. Two notable formulations are the MillerâTuckerâZemlin (MTZ) formulation and the DantzigâFulkersonâJohnson (DFJ) formulation. The DFJ formulation is stronger, though the MTZ formulation is still useful in certain settings.
514:
machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single-machine job sequencing
6968:, 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
337:
remained the method with the best worst-case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs. In 2020 this tiny improvement was extended to the full (metric) TSP.
6700:
5463:
3360:
constraintâensures that no proper subset Q can form a sub-tour, so the solution returned is a single tour and not the union of smaller tours. Because this leads to an exponential number of possible constraints, in practice it is solved with
522:, also known as the "travelling politician problem", deals with "states" that have (one or more) "cities", and the salesman must visit exactly one city from each state. One application is encountered in ordering a solution to the
4167:
where two of the removed edges are adjacent. This so-called two-and-a-half-opt typically falls roughly midway between 2-opt and 3-opt, both in terms of the quality of tours achieved and the time required to achieve those tours.
3677:: a tour of length 66,048,945 units was found, and it was proven that no shorter tour exists. The computation took approximately 15.7 CPU-years (Cook et al. 2006). In April 2006 an instance with 85,900 points was solved using
386:
instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2â3% of an optimal tour.
163:
between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside an
7149:
For benchmarking of TSP algorithms, TSPLIB is a library of sample instances of the TSP and related problems is maintained; see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual
5172:
52:), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an
9267:
Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva; Din, Shahab Ud (December 2018). "Human behaviour in the
Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects".
5620:
4134:
Reassemble the remaining fragments into a tour, leaving no disjoint subtours (that is, do not connect a fragment's endpoints together). This in effect simplifies the TSP under consideration into a much simpler
872:
4729:
3852:
This algorithm looks at things differently by using a result from graph theory which helps improve on the lower bound of the TSP which originated from doubling the cost of the minimum spanning tree. Given an
5737:
9129:
Vickers, Douglas; Mayo, Therese; Heitmann, Megan; Lee, Michael D; Hughes, Peter (2004). "Intelligence and individual differences in performance on three types of visually presented optimisation problems".
2789:
688:
6309:
4323:
depositing pheromone on each edge that they cross, until they have all completed a tour. At this point the ant which completed the shortest tour deposits virtual pheromone along its complete tour route (
771:
It is because these are 0/1 variables that the formulations become integer programs; all other constraints are purely linear. In particular, the objective in the program is to minimize the tour length
6854:
6919:
5097:
of the "ghost" edges linking the ghost nodes to the corresponding original nodes must be low enough to ensure that all ghost edges must belong to any optimal symmetric TSP solution on the new graph (
550:
is how to route data among data processing nodes; routes vary by time to transfer the data, but nodes also differ by their computing power and storage, compounding the problem of where to send data.
506:. A real-world example is avoiding narrow streets with big buses. The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classic example is in
4777:
is called asymmetric TSP. A practical application of an asymmetric TSP is route optimization using street-level routing (which is made asymmetric by one-way streets, slip-roads, motorways, etc.).
6794:
3849:. As a matter of fact, the term "algorithm" was not commonly extended to approximation algorithms until later; the Christofides algorithm was initially referred to as the Christofides heuristic.
2927:
2250:
4591:
obeys the triangle inequality, so the Euclidean TSP forms a special case of metric TSP. However, even when the input points have integer coordinates, their distances generally take the form of
1947:
8978:
Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 March 2003). "Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies".
6477:
3996:
technique involves iteratively removing two edges and replacing them with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. Similarly, the
6000:
1162:
1055:
431:(i.e., each pair of vertices is connected by an edge). If no path exists between two cities, then adding a sufficiently long edge will complete the graph without affecting the optimal tour.
4015:
For Euclidean instances, 2-opt heuristics give on average solutions that are about 5% better than those yielded by Christofides' algorithm. If we start with an initial solution made with a
3705:. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are, with a high probability, just 2â3% away from the optimal solution.
7321:"Der Handlungsreisende â wie er sein soll und was er zu tun hat, um AuftrĂ€ge zu erhalten und eines glĂŒcklichen Erfolgs in seinen GeschĂ€ften gewiĂ zu sein â von einem alten Commis-Voyageur"
3894:
time, so if we had an Eulerian graph with cities from a TSP as vertices, then we can easily see that we could use such a method for finding an Eulerian tour to find a TSP solution. By the
7051:
travelling salesman tour is approximable within 63/38. If the distance function is symmetric, then the longest tour can be approximated within 4/3 by a deterministic algorithm and within
5539:
6063:
5212:
455:. Traffic congestion, one-way streets, and airfares for cities with different departure and arrival fees are real-world considerations that could yield a TSP problem in asymmetric form.
132:
are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%.
9157:
Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva (12 June 2017). "Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem".
5864:
4458:
2000:
6030:
3717:
1737:
358:
Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2,392 cities, using cutting planes and
8671:(1987). On approximation preserving reductions: Complete problems and robust measures' (Report). Department of Computer Science, University of Helsinki. Technical Report C-1987â28.
6466:
6095:
7089:
5809:
5298:
4200:
3608:
3780:
3505:
1642:
8933:
Dry, Matthew; Lee, Michael D.; Vickers, Douglas; Hughes, Peter (2006). "Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes".
4343:
924:
7042:
6235:
3809:, where the second matching is executed after deleting all the edges of the first matching, to yield a set of cycles. The cycles are then stitched to produce the final tour.
1781:
1377:
1203:
5946:
5389:
3550:
3499:
1287:
1093:
6358:
6148:
5890:
5763:
5683:
3590:
7275:
LabbĂ©, Martine; Laporte, Gilbert; MartĂn, Inmaculada RodrĂguez; GonzĂĄlez, Juan JosĂ© Salazar (May 2004). "The Ring Star Problem: Polyhedral analysis and exact algorithm".
5914:
4096:
2906:
640:
604:
6738:
6608:
5403:
1820:
1678:
4627:
points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly.
4255:
3954:
2065:
962:. Therefore, both formulations also have the constraints that, at each vertex, there is exactly one incoming edge and one outgoing edge, which may be expressed as the
960:
5640:
5488:
4553:
2122:
1855:
1450:
1249:
7638:
Rego, CĂ©sar; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), "Traveling salesman problem heuristics: leading methods, implementations and latest advances",
6413:
6195:
3438:
2151:
2092:
1569:
1504:
1477:
1314:
536:. Noon and Bean demonstrated that the generalized travelling salesman problem can be transformed into a standard TSP with the same number of cities, but a modified
176:
The origins of the travelling salesperson problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through
5357:
4048:
3890:
1591:
243:
generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling salesman problem" was the 1949
8076:
Zverovitch, Alexei; Zhang, Weixiong; Yeo, Anders; McGeoch, Lyle A.; Gutin, Gregory; Johnson, David S. (2007), "Experimental Analysis of Heuristics for the ATSP",
6386:
2029:
2214:
2191:
1547:
1420:
983:
6168:
5318:
2234:
2171:
1524:
1397:
1335:
680:
660:
325:
of the graph and then double all its edges, which produces the bound that the length of an optimal tour is at most twice the weight of a minimum spanning tree.
10534:
Medvedev, Andrei; Lee, Michael; Butavicius, Marcus; Vickers, Douglas (1 February 2001). "Human performance on visually presented Traveling Salesman problems".
7168:, by director Timothy Lanzone, is the story of four mathematicians hired by the U.S. government to solve the most elusive problem in computer-science history:
7764:
Velednitsky, Mark (2017). "Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem".
926:
will effectively range over all subsets of the set of edges, which is very far from the sets of edges in a tour, and allows for a trivial minimum where all
9844:
Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs",
5101:= 0 is not always low enough). As a consequence, in the optimal symmetric tour, each original node appears next to its ghost node (e.g. a possible path is
9406:
1208:
These ensure that the chosen set of edges locally looks like that of a tour, but still allow for solutions violating the global requirement that there is
7323:(The travelling salesman â how he must be and what he should do in order to get commissions and be sure of the happy success in his business â by an old
472:(where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a
7704:
Behzad, Arash; Modarres, Mohammad (2002), "New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem",
3898:, we know that the TSP tour can be no longer than the Eulerian tour, and we therefore have a lower bound for the TSP. Such a method is described below.
8651:
9763:
10187:
Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert (2005), "Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem",
7474:
van Bevern, René; Slugina, Viktoriia A. (2020). "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem".
10751:
10625:
Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Philip M. II (1977). "An Analysis of Several Heuristics for the Traveling Salesman Problem".
3631:); this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities, see
3611:
Solution of a TSP with 7 cities using a simple Branch and bound algorithm. Note: The number of permutations is much less than Brute force search
9816:
4785:
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3Ă3 matrix containing all possible path weights between the nodes
219:, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:
10127:
7008:
6999:
If the distances are restricted to 1 and 2 (but still are a metric), then the approximation ratio becomes 8/7. In the asymmetric case with
4235:
algorithms which use local searching heuristic sub-algorithms can find a route extremely close to the optimal route for 700 to 800 cities.
8141:
Ray, S. S.; Bandyopadhyay, S.; Pal, S. K. (2007). "Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering".
9354:
Gibson, Brett; Wilkinson, Matthew; Kelly, Debbie (1 May 2012). "Let the pigeon drive the bus: pigeons can plan future routes in a room".
5548:
4587:
of the points. Any non-optimal solution with crossings can be made into a shorter solution without crossings by local optimizations. The
777:
7141:
adapts its morphology to create an efficient path between the food sources, which can also be viewed as an approximate solution to TSP.
543:
The sequential ordering problem deals with the problem of visiting a set of cities, where precedence relations between the cities exist.
9925:
Padberg, M.; Rinaldi, G. (1991), "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems",
4648:
4346:
Ant colony optimization algorithm for a TSP with 7 cities: Red and thick lines in the pheromone map indicate presence of more pheromone
4191:
2862:{\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}
761:{\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}
17:
10582:(1999), "Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP,
5695:
5174:), and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example,
3732:) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For
4638:
is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/
7640:
5104:
7549:
6246:
4761:
In most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance from
5243:
254:
In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after the
10761:
7120:
6981:
6805:
4327:). The amount of pheromone deposited is inversely proportional to the tour length: the shorter the tour, the more it deposits.
3911:
Convert to TSP: if a city is visited twice, then create a shortcut from the city before this in the tour to the one after this.
6873:
4150:
total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2
120:
The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a
10756:
10486:
10444:
10389:
10362:
10290:
10227:
9907:
9749:
9527:
8824:
8766:
8103:
7931:
7612:
7395:
6961:
6796:, which seem to be good up to more or less 1%. In particular, David S. Johnson obtained a lower bound by computer experiment:
495:
7438:
A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in
10726:
10217:
9627:
8214:
4735:
6743:
36:
Solution of a travelling salesperson problem: the black line shows the shortest possible loop that connects every red dot.
10741:
10681:
7733:
Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)
7215:
6586:{\displaystyle \mathbb {E} \geq {\bigl (}{\tfrac {1}{4}}+{\tfrac {3}{8}}{\bigr )}{\sqrt {n}}={\tfrac {5}{8}}{\sqrt {n}},}
6861:
where 0.522 comes from the points near the square boundary which have fewer neighbours, and Christine L. Valenzuela and
9994:
8604:
4287:
1863:
4486:
In the rectilinear TSP, the distance between two cities is the sum of the absolute values of the differences of their
3508:
Solution to a symmetric TSP with 7 cities using brute force search. Note: Number of permutations: (7−1)!/2 = 360
9495:
8326:
7751:
5954:
4154:-city TSP can then be solved with brute-force methods to find the least-cost recombination of the original fragments.
1098:
991:
355:
of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.
211:. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at
9210:"Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem"
7910:
Ambainis, Andris; Balodis, Kaspars; Iraids, JÄnis; Kokainis, Martins; PrĆ«sis, KriĆĄjÄnis; Vihrovs, JevgÄnijs (2019).
7835:
C. E. Miller, A. W. Tucker, and R. A. Zemlin. 1960. Integer Programming Formulation of Traveling Salesman Problems.
3837:
follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight
3783:
obtained by the NN algorithm for further improvement in an elitist model, where only better solutions are accepted.
3501:. This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach.
10457:; McGeoch, L. A. (1997), "The Traveling Salesman Problem: A Case Study in Local Optimization", in Aarts, E. H. L.;
10462:
8017:
5493:
7852:
Dantzig, G.; Fulkerson, R.; Johnson, S. (November 1954). "Solution of a Large-Scale Traveling-Salesman Problem".
7577:; Klein, Nathan; Gharan, Shayan Oveis (2021), "A (slightly) improved approximation algorithm for metric TSP", in
7164:
6035:
5177:
4608:
3960:
even order, which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov:
484:
419:, and a path's distance is the edge's weight. It is a minimization problem starting and finishing at a specified
299:
87:
8602:(1991). "Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem".
7683:
7111:
was devoted to the topic of human performance on TSP, and a 2011 review listed dozens of papers on the subject.
9307:
3512:
Improving these time bounds seems to be difficult. For example, it has not been determined whether a classical
3391:
Finding special cases for the problem ("subproblems") for which either better or exact heuristics are possible.
416:
7809:
BektaĆ, Tolga; Gouveia, Luis (2014). "Requiem for the MillerâTuckerâZemlin subtour elimination constraints?".
7210:
5823:
4401:
10731:
10312:
10040:
Serdyukov, A. I. (1984), "An algorithm with an estimate for the traveling salesman problem of the maximum'",
7582:
7240:
1952:
9779:, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh
9675:
Bellman, R. (1960), "Combinatorial Processes and Dynamic Programming", in Bellman, R.; Hall, M. Jr. (eds.),
9581:
8648:
7003:, in 2018, a constant factor approximation was developed by Svensson, Tarnawski, and VĂ©gh. An algorithm by
6005:
1686:
6418:
6071:
3845:, and was in part responsible for drawing attention to approximation algorithms as a practical approach to
3694:
3385:
408:
103:
61:
8417:
Jonker, Roy; Volgenant, Ton (1983). "Transforming asymmetric into symmetric traveling salesman problems".
7054:
3720:
Nearest Neighbour algorithm for a TSP with 7 cities. The solution changes as the starting point is changed
8419:
7587:
STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
7338:
5768:
5542:
5257:
4116:
3725:
554:
168:. In many applications, additional constraints such as limited resources or time windows may be imposed.
114:
72:
4887:, linked to the original node with a "ghost" edge of very low (possibly negative) weight, here denoted â
4311:). It models behavior observed in real ants to find short paths between food sources and their nest, an
10280:
10240:; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computing with domino-parity inequalities for the TSP",
7972:
7189:
3740:
1601:
57:
9470:
7309:
See the TSP world tour problem which has already been solved to within 0.05% of the optimal solution.
880:
110:
10746:
10736:
9582:"Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems"
7250:
7021:
6964:
is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with
6200:
4517:
The last two metrics appear, for example, in routing a machine that drills a given set of holes in a
4000:
technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of the
1746:
10400:"Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP"
9732:
9560:
8947:
8044:"Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP"
2814:
1342:
1167:
713:
10698:
10616:
10197:
10155:
9799:
8992:
8285:
8155:
8086:
7235:
7199:
5919:
5362:
5223:
4336:
3702:
3519:
3458:
1254:
1060:
499:
488:
477:
469:
9208:
Kyritsis, Markos; Blathras, George; Gulliver, Stephen; Varela, Vasiliki-Alexia (11 January 2017).
8896:
Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem",
8450:(2016), "BeardwoodâHaltonâHammersley theorem for stationary ergodic sequences: a counterexample",
8263:
Dorigo, Marco; Gambardella, Luca Maria (1997). "Ant Colonies for the Traveling Salesman Problem".
7320:
6695:{\displaystyle \mathbb {E} \geq {\bigl (}{\tfrac {5}{8}}+{\tfrac {19}{5184}}{\bigr )}{\sqrt {n}},}
6320:
6110:
5869:
5742:
5645:
5458:{\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta \qquad {\text{when }}n\to \infty ,}
4895:. In the new graph, no edge directly links original nodes and no edge directly links ghost nodes.
3559:
7230:
5895:
4300:
4292:
4251:
4101:
4057:
3917:
3842:
3806:
3698:
3452:
2875:
2173:
for each step along a tour, with a decrease only allowed where the tour passes through city
609:
577:
76:
32:
10176:
9895:
8186:
Kahng, A. B.; Reda, S. (2004). "Match Twice and Stitch: A New TSP Tour Construction Heuristic".
4505:, the distance between two points is the maximum of the absolute values of differences of their
10689:
10611:
10192:
10191:, Cahiers du GERAD, G-2005-02 (3), Montreal: Group for Research in Decision Analysis: 402â407,
10150:
9954:
9794:
9727:
9555:
8987:
8942:
8280:
8150:
8081:
6993:
6711:
5391:
be the shortest path length (i.e. TSP solution) for this set of points, according to the usual
4238:
TSP is a touchstone for many general heuristics devised for combinatorial optimization such as
4208:
3834:
3802:
1786:
1647:
333:
275:
196:
10704:
9721:
3923:
2153:
variables then enforce that a single tour visits all cities is that they increase by at least
2034:
929:
10579:
10496:
MacGregor, J. N.; Ormerod, T. (1996), "Human performance on the traveling salesman problem",
10372:
Goldberg, D. E. (1989), "Genetic Algorithms in Search, Optimization & Machine Learning",
10106:
Combinatorial Optimization â Eureka, You Shrink! Lecture notes in computer science, vol. 2570
9082:"Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem"
8324:
Quintas, L. V.; Supnick, Fred (1965). "On some properties of shortest Hamiltonian circuits".
7151:
7137:
4743:
4518:
4375:
A very natural restriction of the TSP is to require that the distances between cities form a
523:
507:
480:, which only asks if a Hamiltonian path (or cycle) exists in a non-complete unweighted graph.
424:
420:
412:
322:
267:
121:
10664:
10606:
Rao, S.; Smith, W. (1998). "Approximating geometrical graphs via 'spanners' and 'banyans'".
8707:
7988:
Applegate, David; Bixby, Robert; ChvĂĄtal, VaĆĄek; Cook, William; Helsgaun, Keld (June 2004).
7520:
5625:
5473:
4528:
2097:
1825:
1425:
1224:
298:
published an article entitled "The Shortest Path Through Many Points" in the journal of the
10377:
10264:
10142:
10101:
10073:
9980:
9639:
9610:
9427:
9221:
8355:
8272:
7661:
7104:
6985:
6391:
6173:
4600:
4376:
4299:
described in 1993 a method of heuristically generating "good solutions" to the TSP using a
4263:
3664:
3640:
3411:
2129:
2070:
1554:
1482:
1455:
1292:
279:
240:
9537:
Allender, Eric; BĂŒrgisser, Peter; Kjeldgaard-Pedersen, Johan; Mitersen, Peter Bro (2007),
8568:
Held, M.; Karp, R.M. (1970). "The Traveling Salesman Problem and Minimum Spanning Trees".
5323:
4024:
3982:
3866:
1576:
124:
for many optimization methods. Even though the problem is computationally difficult, many
8:
10694:
10015:
9444:
8747:"A constant-factor approximation algorithm for the asymmetric traveling salesman problem"
7976:
7911:
7000:
6969:
6363:
5811:
are replaced with observations from a stationary ergodic process with uniform marginals.
4380:
4369:
4243:
3895:
3846:
3841:. This gives a TSP tour which is at most 1.5 times the optimal. It was one of the first
3795:
3673:
3448:
2008:
568:
503:
65:
10381:
10146:
10077:
9685:
Bellman, R. (1962), "Dynamic Programming Treatment of the Travelling Salesman Problem",
9643:
9538:
9431:
9225:
8374:
8276:
6708:
Held and Karp gave a polynomial-time algorithm that provides numerical lower bounds for
4468:
on the set of vertices. When the cities are viewed as points in the plane, many natural
3825:
3667:. The total computation time was equivalent to 22.6 years on a single 500 MHz
2196:
2176:
1529:
1402:
965:
451:, paths may not exist in both directions or the distances might be different, forming a
155:
represents, for example, customers, soldering points, or DNA fragments, and the concept
10642:
10567:
10523:
10340:
10332:
10202:
10089:
10063:
9989:
9942:
9863:
9854:
Karpinski, M.; Lampis, M.; Schmied, R. (2015), "New Inapproximability bounds for TSP",
9755:
9704:
9663:
9614:
9589:
9417:
9387:
9285:
9244:
9209:
9190:
9021:
8830:
8802:
8772:
8599:
8477:
8459:
8343:
8306:
8245:
8168:
7937:
7791:
7773:
7665:
7618:
7590:
7501:
7483:
7100:
6965:
6153:
5392:
5303:
4588:
4495:
4480:
4259:
3656:
3617:
3444:
of the number of cities, so this solution becomes impractical even for only 20 cities.
3405:
2219:
2156:
1509:
1382:
1320:
665:
645:
374:
329:
212:
160:
144:
10416:
10399:
9884:
Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), "Long tours and short superstrings'",
9808:
9143:
8746:
8294:
8060:
8043:
7255:
2193:
That constraint would be violated by every tour which does not pass through city
332:
and Serdyukov (independently of each other) made a big advance in this direction: the
10559:
10551:
10515:
10482:
10458:
10440:
10421:
10385:
10358:
10308:
10286:
10223:
10168:
10093:
9971:
9913:
9903:
9745:
9667:
9655:
9523:
9379:
9371:
9249:
9182:
9174:
9111:
9103:
9062:
9013:
9005:
8960:
8915:
8834:
8820:
8762:
8541:
8524:
8447:
8432:
8298:
8237:
8099:
8024:
7927:
7747:
7622:
7608:
7505:
7391:
7292:
5235:
4469:
4239:
3652:
2239:
The MTZ formulation of TSP is thus the following integer linear programming problem:
473:
443:, the distance between two cities is the same in each opposite direction, forming an
344:
291:
271:
195:
The TSP was mathematically formulated in the 19th century by the Irish mathematician
80:
10646:
10527:
10344:
9946:
9708:
9391:
9289:
9025:
8776:
8249:
8215:"Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods"
7941:
4883:
To double the size, each of the nodes in the graph is duplicated, creating a second
262:
offered prizes for steps in solving the problem. Notable contributions were made by
10634:
10595:
10571:
10543:
10505:
10454:
10411:
10324:
10268:
10260:
10249:
10160:
10081:
10023:
10003:
9966:
9934:
9873:
9832:
9804:
9759:
9737:
9694:
9647:
9618:
9598:
9565:
9363:
9319:
9277:
9239:
9229:
9194:
9166:
9139:
9093:
9052:
8997:
8952:
8905:
8812:
8754:
8613:
8577:
8536:
8505:
8481:
8469:
8428:
8335:
8310:
8290:
8229:
8195:
8172:
8160:
8123:
8091:
8055:
8013:
7919:
7861:
7818:
7795:
7783:
7706:
Proceedings of the 15th International Conference of Systems Engineering (Las Vegas)
7669:
7649:
7600:
7493:
7284:
7220:
7115:
6945:
6941:
6937:
6862:
4584:
4016:
3838:
3791:
3729:
3624:
3600:
444:
359:
310:
284:
255:
244:
232:
208:
10608:
STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing
9234:
3639:
An exact solution for 15,112 German towns from TSPLIB was found in 2001 using the
1316:
that keeps track of the order in which the cities are visited, counting from city
187:
10685:
10666:
A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem
10476:
10434:
10352:
10304:
10276:
10237:
10213:
10123:
9976:
9717:
9606:
9546:
9515:
9281:
8794:
8655:
8351:
7657:
7545:
7412:
7385:
7205:
7194:
7176:
5231:
4596:
4576:
4195:
4008:
is an often heard misnomer for 2-opt; LinâKernighan is actually the more general
3668:
3660:
3648:
3553:
3513:
3378:
574:
Common to both these formulations is that one labels the cities with the numbers
537:
519:
378:
370:
366:
340:
295:
236:
165:
129:
106:
99:
10054:
Steinerberger, Stefan (2015), "New Bounds for the Traveling Salesman Constant",
10027:
8222:
Proceedings of the International Conference on Automated Planning and Scheduling
7923:
7521:"Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem"
10300:
10272:
9877:
9767:
8668:
8595:
7822:
7653:
7225:
4580:
4502:
3854:
3644:
3628:
3362:
2916:. Then TSP can be written as the following integer linear programming problem:
452:
428:
263:
248:
200:
148:
10599:
10219:
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
9651:
9367:
9170:
9080:
MacGregor, James N.; Chronicle, Edward P.; Ormerod, Thomas C. (1 March 2004).
8509:
8233:
8199:
8164:
7966:
7787:
6972:, a shortcut that skips a repeated visit would not increase the tour length).
5238:(that is, when is there a curve with finite length that visits every point in
4747:
532:
10720:
10555:
10425:
10085:
9659:
9577:
9375:
9338:
9178:
9107:
9066:
9009:
8964:
8241:
8095:
7916:
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
7578:
7497:
7296:
7013:
5892:, by using a naĂŻve path which visits monotonically the points inside each of
5689:
4739:
4556:
4216:
4215:-opting the new tour. The mutation is often enough to move the tour from the
3858:
3603:
algorithms, which can be used to process TSPs containing thousands of cities.
527:
94:, the task is to decide whether the graph has a tour whose length is at most
10475:
Lawler, E. L.; Shmoys, D. B.; Kan, A. H. G. Rinnooy; Lenstra, J. K. (1985).
10164:
9741:
9536:
9308:"Human performance on the traveling salesman and related problems: A review"
9041:"Human Performance on the Traveling Salesman and Related Problems: A Review"
8816:
8758:
8494:
Few, L. (1955). "The shortest path and the shortest road through n points".
8380:
7604:
7387:
The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization
4753:
In practice, simpler heuristics with weaker guarantees continue to be used.
3659:. The computations were performed on a network of 110 processors located at
3388:, i.e., algorithms that deliver approximated solutions in a reasonable time.
3373:
The traditional lines of attack for the NP-hard problems are the following:
10563:
10253:
10019:
9917:
9896:"6.4.7: Applications of Network Models § Routing Problems §§ Euclidean TSP"
9820:
9383:
9324:
9253:
9186:
9115:
9057:
9040:
9017:
8956:
8581:
7989:
4472:
are metrics, and so many natural instances of TSP satisfy this constraint.
4465:
4316:
4296:
4232:
3787:
3701:, which quickly yield good solutions, have been devised. These include the
465:
305:
In the following decades, the problem was studied by many researchers from
259:
204:
10547:
10519:
10172:
9777:
Worst-case analysis of a new heuristic for the travelling salesman problem
9699:
9602:
8919:
8799:
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
8751:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
8302:
7310:
526:
in order to minimize knife changes. Another is concerned with drilling in
10328:
9677:
Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10
8617:
8496:
7865:
7574:
7245:
6957:
4592:
4479:
In the Euclidean TSP (see below), the distance between two cities is the
4275:
4247:
4204:
3794:
that has the points as its vertices; it can be computed efficiently with
3408:). The running time for this approach lies within a polynomial factor of
3401:
348:
306:
216:
181:
135:
The TSP has several applications even in its purest formulation, such as
53:
10007:
9785:
Hassin, R.; Rubinstein, S. (2000), "Better approximations for max TSP",
9471:"'Travelling Salesman' movie considers the repercussions if P equals NP"
8525:"A parallel tabu search algorithm for large traveling salesman problems"
8127:
7840:
4750:
in 2010 for their concurrent discovery of a PTAS for the Euclidean TSP.
3616:
Progressive improvement algorithms, which use techniques reminiscent of
147:. Slightly modified, it appears as a sub-problem in many areas, such as
10510:
10206:
10018:(2005). "On the history of combinatorial optimization (till 1960)". In
9098:
9081:
9001:
8910:
8790:
8473:
8347:
8118:
Rosenkrantz, D. J.; Stearns, R. E.; Lewis, P. M. (14â16 October 1974).
7452:
7450:
7448:
7336:
A discussion of the early work of Hamilton and Kirkman can be found in
7118:
titled "Let the Pigeon Drive the Bus," named after the children's book
7004:
4603:
needed to perform exact comparisons of the lengths of different tours.
10354:
Computers and Intractability: A Guide to the Theory of NP-completeness
10336:
9569:
8213:
Alatartsev, Sergey; Augustine, Marcus; Ortmeier, Frank (2 June 2013).
8122:. 15th Annual Symposium on Switching and Automata Theory (swat 1974).
8080:, Combinatorial Optimization, Springer, Boston, MA, pp. 445â487,
7975:. How to cut unfruitful branches using reduced rows and columns as in
7912:"Quantum Speedups for Exponential-Time Dynamic Programming Algorithms"
7288:
7103:
variant of the problem, has attracted the attention of researchers in
3967:
Create a matching for the problem with the set of cities of odd order.
3817:
483:
The requirement of returning to the starting city does not change the
10633:(5). SIAM (Society for Industrial and Applied Mathematics): 563â581.
9992:(1993), "The traveling salesman problem with distances one and two",
5320:
independent random variables with uniform distribution in the square
4312:
4163:
3829:
Using a shortcut heuristic on the graph created by the matching above
3441:
314:
140:
125:
10638:
9938:
9836:
9407:"Computation of the travelling salesman problem by a shrinking blob"
8339:
8018:"The Traveling Salesman Problem: A Case Study in Local Optimization"
7445:
6980:
In the general case, finding a shortest travelling salesman tour is
5249:
4475:
The following are some examples of metric TSPs for various metrics.
4178:
The variable-opt method is related to, and a generalization of, the
9957:(1977), "The Euclidean traveling salesman problem is NP-complete",
8807:
8675:
8631:
7778:
7595:
7488:
7169:
5615:{\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} /{\sqrt {n}}}
1506:
equal to the number of edges along that tour, when going from city
867:{\displaystyle \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}.}
558:
purchasing cost) and enables the purchase of all required products.
136:
10068:
9868:
9422:
8841:
8464:
8042:
Gutina, Gregory; Yeob, Anders; Zverovich, Alexey (15 March 2002).
7420:(Technical report). Santa Monica, CA: The RAND Corporation. RM-303
4579:, the optimal solution to the travelling salesman problem forms a
4019:, then the average number of moves greatly decreases again and is
3716:
2771:
or more disjointed tours that only collectively cover all cities.
9843:
9823:(1962), "A Dynamic Programming Approach to Sequencing Problems",
7132:
When presented with a spatial configuration of food sources, the
6933:
4724:{\displaystyle O{\left(n(\log n)^{O(c{\sqrt {d}})^{d-1}}\right)}}
4123:-opt or variable-opt technique. It involves the following steps:
3737:
et al. showed that the NN algorithm has the approximation factor
2216:
so the only way to satisfy it is that the tour passing city
352:
318:
177:
8753:. Stoc 2018. Los Angeles, CA, USA: ACM Press. pp. 204â213.
5732:{\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }
447:. This symmetry halves the number of possible solutions. In the
9723:
Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06)
7133:
4107:
547:
10351:
Garey, Michael R.; Johnson, David S. (1979). "A2.3: ND22â24".
10128:"Molecular Computation of Solutions To Combinatorial Problems"
9626:
Beardwood, J.; Halton, J.H.; Hammersley, J.M. (October 1959),
9207:
3812:
3607:
399:
9825:
Journal of the Society for Industrial and Applied Mathematics
8853:
7909:
5226:
which asks the following: under what conditions may a subset
5167:{\displaystyle \mathrm {A\to A'\to C\to C'\to B\to B'\to A} }
4335:
the bad solutions disappear. The map is a work of Yves Aubry
4052:; however, for random starts, the average number of moves is
3997:
3992:
3905:
Create duplicates for every edge to create an Eulerian graph.
3504:
511:
10533:
8877:
8120:
Approximate algorithms for the traveling salesperson problem
6304:{\displaystyle \mathbb {E} \geq {\tfrac {1}{2}}{\sqrt {n}}.}
4342:
3404:(ordered combinations) and see which one is cheapest (using
251:, "On the Hamiltonian game (a traveling salesman problem)."
10104:(2003), "Exact Algorithms for NP-Hard Problems: A Survey",
9266:
8726:
8212:
7390:(Repr. with corrections. ed.). John Wiley & sons.
5490:
is a positive constant that is not known explicitly. Since
2855:
1551:
Because linear programming favors non-strict inequalities (
754:
274:
from the RAND Corporation, who expressed the problem as an
10259:
7948:
7274:
6952:, decide whether there is a round-trip route cheaper than
3381:, which work reasonably fast only for small problem sizes.
562:
9625:
9513:
9079:
8745:
Svensson, Ola; Tarnawski, Jakub; VĂ©gh, LĂĄszlĂł A. (2018).
8549:
8362:
8075:
7987:
7456:
6989:
6849:{\displaystyle L_{n}^{*}\gtrsim 0.7080{\sqrt {n}}+0.522,}
3688:
3682:
3632:
10656:
A Multilevel Approach to the Travelling Salesman Problem
9886:
Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci
9156:
8687:
7637:
7550:"Computer Scientists Break Traveling Salesperson Record"
6914:{\displaystyle L_{n}^{*}\gtrsim 0.7078{\sqrt {n}}+0.551}
4315:
behavior resulting from each ant's preference to follow
3805:, Match Twice and Stitch (MTS), performs two sequential
2774:
90:, the decision version of the TSP (where given a length
10624:
10299:
9987:
8681:
8386:
8117:
7851:
4203:) build on the LinâKernighan method, adding ideas from
1595:
we would like to impose constraints to the effect that
235:
who was looking to solve a school bus routing problem.
231:
It was first considered mathematically in the 1930s by
10711:
10474:
10313:"Solution of a large-scale traveling salesman problem"
9853:
9846:
In Proc. 44th IEEE Symp. on Foundations of Comput. Sci
9128:
8847:
7717:
7414:
On the Hamiltonian game (a traveling salesman problem)
7047:
The corresponding maximization problem of finding the
6664:
6649:
6562:
6533:
6518:
6280:
4642:) times the optimal for geometric instances of TSP in
10236:
10186:
9720:(2006), "8/7-approximation algorithm for (1,2)-TSP",
8865:
8744:
7891:
7854:
Journal of the Operations Research Society of America
7720:
Combinatorial optimization: algorithms and complexity
7057:
7024:
6876:
6808:
6746:
6714:
6611:
6480:
6421:
6394:
6366:
6323:
6249:
6203:
6176:
6156:
6113:
6074:
6038:
6008:
5957:
5922:
5898:
5872:
5826:
5771:
5745:
5698:
5648:
5628:
5551:
5496:
5476:
5406:
5365:
5326:
5306:
5260:
5180:
5107:
4797:. One option is to turn an asymmetric matrix of size
4651:
4531:
4404:
4162:-opt methods are 3-opt, as introduced by Shen Lin of
4060:
4027:
3926:
3869:
3743:
3562:
3522:
3461:
3414:
2925:
2878:
2792:
2248:
2222:
2199:
2179:
2159:
2132:
2100:
2073:
2037:
2011:
1955:
1866:
1828:
1789:
1749:
1689:
1650:
1604:
1579:
1557:
1532:
1512:
1485:
1458:
1428:
1405:
1385:
1345:
1323:
1295:
1257:
1227:
1170:
1101:
1063:
994:
968:
932:
883:
780:
691:
668:
648:
612:
580:
476:
with the least weight. This is more general than the
10708:
by Jon McLoone at the Wolfram Demonstrations Project
9353:
8031:. London: John Wiley and Sons Ltd. pp. 215â310.
7342:
by Biggs, Lloyd, and Wilson (Clarendon Press, 1986).
6865:
obtained the following other numerical lower bound:
6789:{\displaystyle \beta (\simeq L_{n}^{*}/{\sqrt {n}})}
3356:
The last constraint of the DFJ formulationâcalled a
10398:Gutin, G.; Yeo, A.; Zverovich, A. (15 March 2002).
8977:
8932:
8140:
8041:
7175:Solutions to the problem are used by mathematician
7044:. The best known inapproximability bound is 75/74.
6317:A better lower bound is obtained by observing that
4269:
1452:variables), one may find satisfying values for the
1216:
9687:Journal of the Association for Computing Machinery
9632:Proceedings of the Cambridge Philosophical Society
9499:By Evelyn Lamb, Scientific American, 31 April 2015
7083:
7036:
6913:
6848:
6788:
6732:
6694:
6585:
6460:
6407:
6380:
6352:
6303:
6229:
6189:
6162:
6142:
6089:
6057:
6024:
5994:
5940:
5908:
5884:
5858:
5803:
5757:
5731:
5677:
5634:
5614:
5533:
5482:
5457:
5383:
5351:
5312:
5292:
5206:
5166:
4723:
4547:
4452:
4090:
4042:
3948:
3884:
3774:
3584:
3544:
3493:
3432:
3345:
2900:
2861:
2759:
2228:
2208:
2185:
2165:
2145:
2116:
2086:
2059:
2023:
1994:
1941:
1849:
1814:
1775:
1731:
1672:
1636:
1585:
1563:
1541:
1518:
1498:
1471:
1444:
1414:
1391:
1371:
1329:
1308:
1281:
1243:
1197:
1156:
1087:
1049:
977:
954:
918:
866:
760:
674:
654:
634:
598:
10436:The Traveling Salesman Problem and Its Variations
10397:
9883:
9679:, American Mathematical Society, pp. 217â249
8859:
8398:
8262:
8078:The Traveling Salesman Problem and Its Variations
7573:
7473:
7428:– via Defense Technical Information Center.
6068:Fietcher empirically suggested an upper bound of
5250:Path length for random sets of points in a square
4391:is never farther than the route via intermediate
3708:Several categories of heuristics are recognized.
1942:{\displaystyle u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})}
10718:
10495:
9784:
8895:
8883:
8594:
5559:
2930:
2253:
1422:For a given tour (as encoded into values of the
10285:(2nd ed.). MIT Press. pp. 1027â1033.
10189:The Journal of the Operational Research Society
9715:
8732:
8416:
7094:
5995:{\displaystyle L_{n}^{*}\leq {\sqrt {2n}}+1.75}
1157:{\displaystyle \sum _{j=1,j\neq i}^{n}x_{ij}=1}
1050:{\displaystyle \sum _{i=1,i\neq j}^{n}x_{ij}=1}
10453:
9924:
9404:
8801:. Stoc 2020. Chicago, IL: ACM. pp. 1â13.
8795:"An improved approximation algorithm for ATSP"
8666:
8323:
8012:
7954:
7703:
6975:
4494:-coordinates. This metric is often called the
4368:or Î-TSP, the intercity distances satisfy the
682:. The main variables in the formulations are:
10053:
9953:
9894:Larson, Richard C.; Odoni, Amedeo R. (1981),
9514:Applegate, D. L.; Bixby, R. M.; ChvĂĄtal, V.;
8555:
8445:
8368:
7968:Traveling Salesman Problem - Branch and Bound
7808:
6677:
6643:
6546:
6512:
3964:Find a minimum spanning tree for the problem.
3902:Find a minimum spanning tree for the problem.
3400:The most direct solution would be to try all
207:was a recreational puzzle based on finding a
27:NP-hard problem in combinatorial optimization
10470:, John Wiley and Sons Ltd., pp. 215â310
10350:
9774:
9305:
9038:
8708:"Đ ĐœĐ”ĐșĐŸŃĐŸŃŃŃ
ŃĐșŃŃŃĐ”ĐŒĐ°Đ»ŃĐœŃŃ
ĐŸĐ±Ń
ĐŸĐŽĐ°Ń
ĐČ ĐłŃĐ°ŃĐ°Ń
"
8693:
8649:Christine L. Valenzuela and Antonia J. Jones
7432:
5534:{\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}
3790:of a set of points is the minimum-perimeter
3556:for TSP due to Ambainis et al. runs in time
3314:
3296:
2383:
2371:
1986:
1968:
901:
884:
510:manufacturing: scheduling of a route of the
10432:
9893:
8710:[On some extremal walks in graphs]
8392:
7763:
7718:Papadimitriou, C.H.; Steiglitz, K. (1998),
7404:
6994:the algorithm of Christofides and Serdyukov
6927:
6058:{\displaystyle \beta \leq 0.984{\sqrt {2}}}
5765:may not exist if the independent locations
5207:{\displaystyle \mathrm {A\to C\to B\to A} }
4138:Each fragment endpoint can be connected to
4111:-opt heuristic, or LinâKernighan heuristics
4104:heuristics to re-optimize route solutions.
3813:The Algorithm of Christofides and Serdyukov
434:
10464:Local Search in Combinatorial Optimisation
8789:
8029:Local Search in Combinatorial Optimisation
8008:
8006:
7686:How Do You Fix School Bus Routes? Call MIT
6988:(and thus symmetric), the problem becomes
6415:and the closest and second closest points
4780:
4281:
3711:
2779:Label the cities with the numbers 1, ...,
1822:which is not correct. Instead MTZ use the
502:with the minimal weight of the weightiest
184:, but contains no mathematical treatment.
159:represents travelling times or cost, or a
10615:
10509:
10415:
10196:
10154:
10100:
10067:
10039:
10014:
9970:
9888:, IEEE Computer Society, pp. 166â177
9867:
9798:
9731:
9698:
9559:
9539:"On the Complexity of Numerical Analysis"
9421:
9323:
9243:
9233:
9097:
9056:
8991:
8946:
8909:
8871:
8806:
8705:
8540:
8463:
8284:
8185:
8154:
8085:
8059:
7897:
7777:
7746:, Princeton, NJ: PrincetonUP, pp. 545â7,
7594:
7544:
7518:
7487:
7457:Beardwood, Halton & Hammersley (1959)
7439:
7352:
7202:(also known as "Chinese postman problem")
6613:
6482:
6325:
6251:
6115:
5650:
5575:
4226:
1743:achieve that, because this also requires
10605:
10578:
10433:Gutin, G.; Punnen, A. P. (18 May 2007).
10371:
9815:
9301:
9299:
8567:
8522:
7886:
7811:European Journal of Operational Research
7641:European Journal of Operational Research
7410:
7268:
6984:-complete. If the distance measure is a
6936:(more precisely, it is complete for the
5859:{\displaystyle L^{*}\leq 2{\sqrt {n}}+2}
4453:{\displaystyle d_{AB}\leq d_{AC}+d_{CB}}
4341:
4274:This starts with a sub-tour such as the
3981:
3824:
3816:
3715:
3606:
3503:
398:
186:
109:for any algorithm for the TSP increases
102:problems. Thus, it is possible that the
31:
10662:
10653:
10481:. John Wiley & Sons, Incorporated.
10122:
9856:Journal of Computer and System Sciences
9684:
9674:
9628:"The Shortest Path Through Many Points"
9405:Jones, Jeff; Adamatzky, Andrew (2014),
8003:
7882:
7878:
7633:
7631:
7469:
7467:
7465:
7379:
7377:
7375:
7373:
7371:
7369:
7367:
7365:
7355:. Original German: "Wir bezeichnen als
6948:version ("given the costs and a number
6388:times the sum of the distances between
3835:algorithm of Christofides and Serdyukov
3620:. This works well for up to 200 cities.
3368:
1995:{\displaystyle i,j\in \{2,\dotsc ,n\},}
563:Integer linear programming formulations
520:generalized travelling salesman problem
287:algorithms perhaps for the first time.
14:
10752:Computational problems in graph theory
10719:
10277:"35.2: The traveling-salesman problem"
9306:MacGregor, James N.; Chu, Yun (2011),
9132:Personality and Individual Differences
9039:MacGregor, James N.; Chu, Yun (2011).
8848:Karpinski, Lampis & Schmied (2015)
8439:
7383:
7127:
6962:bottleneck travelling salesman problem
6237:, one gets (after a short computation)
6025:{\displaystyle \beta \leq {\sqrt {2}}}
4383:; that is, the direct connection from
3920:using algorithms with a complexity of
3689:Heuristic and approximation algorithms
2236:also passes through all other cities.
1732:{\displaystyle u_{j}\geq u_{i}+x_{ij}}
1251:variables as above, there is for each
496:bottleneck travelling salesman problem
464:An equivalent formulation in terms of
10035:. Amsterdam: Elsevier. pp. 1â68.
9576:
9468:
9296:
8682:Papadimitriou & Yannakakis (1993)
8404:
7841:https://doi.org/10.1145/321043.321046
6461:{\displaystyle X_{i},X_{j}\neq X_{0}}
6090:{\displaystyle \beta \leq 0.73\dots }
5244:analyst's travelling salesman problem
4611:, and so can be computed in expected
4599:, making it difficult to perform the
3970:Find an Eulerian tour for this graph.
3908:Find an Eulerian tour for this graph.
3627:and problem-specific cut generation (
2775:DantzigâFulkersonâJohnson formulation
394:
151:. In these applications, the concept
10695:TSPLIB, Sample instances for the TSP
10688: (archived 17 December 2013) at
10212:
7628:
7519:Klarreich, Erica (30 January 2013).
7462:
7362:
7084:{\displaystyle (33+\varepsilon )/25}
6032:, later improved by Karloff (1987):
5217:
4736:polynomial-time approximation scheme
4186:-opt methods remove a fixed number (
3977:
3447:One of the earliest applications of
642:to be the cost (distance) from city
427:exactly once. Often, the model is a
10357:. W. H. Freeman. pp. 211â212.
8493:
7411:Robinson, Julia (5 December 1949).
7216:Steiner travelling salesman problem
7121:Don't Let the Pigeon Drive the Bus!
5804:{\displaystyle X_{1},\ldots ,X_{n}}
5395:. It is known that, almost surely,
5293:{\displaystyle X_{1},\ldots ,X_{n}}
3552:exists. The currently best quantum
3455:, which solves the problem in time
3395:
2067:does not impose a relation between
458:
411:, such that cities are the graph's
24:
10115:
9995:Mathematics of Operations Research
9462:
8605:Mathematics of Operations Research
7157:
5752:
5622:, hence lower and upper bounds on
5569:
5449:
5200:
5194:
5188:
5182:
5160:
5150:
5143:
5133:
5126:
5116:
5109:
4769:is not equal to the distance from
4329:
4288:Ant colony optimization algorithms
4170:
3744:
3287:
88:theory of computational complexity
83:are three generalizations of TSP.
25:
10773:
10675:
10029:Handbook of Discrete Optimization
8860:Kosaraju, Park & Stein (1994)
8452:The Annals of Applied Probability
8327:The American Mathematical Monthly
7744:Linear Programming and Extensions
7351:Cited and English translation in
6932:The problem has been shown to be
6599:The currently-best lower bound is
5222:There is an analogous problem in
4801:into a symmetric matrix of size 2
4483:between the corresponding points.
4278:and then inserts other vertices.
3775:{\displaystyle \Theta (\log |V|)}
3681:, taking over 136 CPU-years; see
1637:{\displaystyle u_{j}\geq u_{i}+1}
877:Without further constraints, the
199:and by the British mathematician
7018:achieves a performance ratio of
5242:)? This problem is known as the
4595:, and the length of a tour is a
4350:
4270:Constricting Insertion Heuristic
3726:nearest neighbour (NN) algorithm
1217:MillerâTuckerâZemlin formulation
919:{\displaystyle \{x_{ij}\}_{i,j}}
567:The TSP can be formulated as an
498:: Find a Hamiltonian cycle in a
423:after having visited each other
334:Christofides-Serdyukov algorithm
10056:Advances in Applied Probability
9488:
9469:Geere, Duncan (26 April 2012).
9437:
9398:
9347:
9332:
9260:
9201:
9150:
9122:
9073:
9032:
8971:
8926:
8889:
8783:
8738:
8706:Serdyukov, Anatoliy I. (1978),
8699:
8660:
8642:
8624:
8588:
8561:
8516:
8487:
8410:
8317:
8256:
8206:
8179:
8134:
8111:
8069:
8035:
7981:
7960:
7903:
7872:
7845:
7839:7, 4 (Oct. 1960), 326â329. DOI:
7829:
7802:
7757:
7736:
7727:
7711:
7697:
7676:
7567:
7538:
7512:
7037:{\displaystyle 22+\varepsilon }
6230:{\displaystyle X_{i}\neq X_{0}}
5437:
4609:Euclidean minimum spanning tree
3986:An example of a 2-opt iteration
3973:Convert to TSP using shortcuts.
2031:provides sufficient slack that
1776:{\displaystyle u_{j}\geq u_{i}}
546:A common interview question at
494:Another related problem is the
300:Cambridge Philosophical Society
10498:Perception & Psychophysics
10478:The Traveling Salesman Problem
10222:. Princeton University Press.
9787:Information Processing Letters
9522:, Princeton University Press,
9520:The Traveling Salesman Problem
9045:The Journal of Problem Solving
8935:The Journal of Problem Solving
8898:Perception & Psychophysics
8884:Hassin & Rubinstein (2000)
7583:Williams, Virginia Vassilevska
7345:
7330:
7314:
7303:
7070:
7058:
6783:
6750:
6635:
6617:
6504:
6486:
6347:
6329:
6273:
6255:
6137:
6119:
6101:
5814:
5749:
5723:
5672:
5654:
5597:
5579:
5566:
5446:
5431:
5340:
5327:
5197:
5191:
5185:
5157:
5146:
5140:
5129:
5123:
5112:
4698:
4684:
4677:
4664:
4085:
4082:
4076:
4064:
4037:
4031:
3943:
3930:
3879:
3873:
3769:
3765:
3757:
3747:
3579:
3566:
3539:
3526:
3488:
3465:
3427:
3418:
3329:
3321:
3274:
3266:
2672:
2650:
2647:
2635:
1936:
1914:
1911:
1899:
1844:
1832:
1372:{\displaystyle u_{i}<u_{j}}
1198:{\displaystyle i=1,\ldots ,n.}
403:Symmetric TSP with four cities
389:
46:travelling salesperson problem
13:
1:
10762:Metaphors referring to people
10586:-MST, and related problems",
10417:10.1016/S0166-218X(01)00195-0
9809:10.1016/S0020-0190(00)00097-1
9506:
9496:When the Mona Lisa is NP-Hard
9344:, 2006, retrieved 2014-06-06.
9235:10.1016/j.heliyon.2017.e00461
9144:10.1016/s0191-8869(03)00200-9
8793:; Vygen, Jens (8 June 2020).
8733:Berman & Karpinski (2006)
8295:10.1016/S0303-2647(97)01708-5
8061:10.1016/S0166-218X(01)00195-0
7241:Mixed Chinese postman problem
7179:in a subgenre called TSP art.
7144:
5941:{\displaystyle 1/{\sqrt {n}}}
5541:(see below), it follows from
5384:{\displaystyle L_{n}^{\ast }}
4756:
4583:through all of the points, a
4219:identified by LinâKernighan.
3545:{\displaystyle O(1.9999^{n})}
3494:{\displaystyle O(n^{2}2^{n})}
2908:to be the distance from city
2824:the path goes from city
1282:{\displaystyle i=1,\ldots ,n}
1088:{\displaystyle j=1,\ldots ,n}
723:the path goes from city
117:) with the number of cities.
10757:Hamiltonian paths and cycles
10404:Discrete Applied Mathematics
10376:, New York: Addison-Wesley,
10242:INFORMS Journal on Computing
10108:, Springer, pp. 185â207
9988:Papadimitriou, Christos H.;
9972:10.1016/0304-3975(77)90012-3
9959:Theoretical Computer Science
9449:comopt.ifi.uni-heidelberg.de
9282:10.1016/j.cogsys.2018.07.027
8542:10.1016/0166-218X(92)00033-I
8433:10.1016/0167-6377(83)90048-2
8048:Discrete Applied Mathematics
7955:Padberg & Rinaldi (1991)
7095:Human and animal performance
6996:approximates it within 1.5.
6353:{\displaystyle \mathbb {E} }
6143:{\displaystyle \mathbb {E} }
5885:{\displaystyle \beta \leq 2}
5758:{\displaystyle n\to \infty }
5678:{\displaystyle \mathbb {E} }
4570:
3585:{\displaystyle O(1.728^{n})}
555:travelling purchaser problem
73:travelling purchaser problem
62:theoretical computer science
7:
10727:Travelling salesman problem
8420:Operations Research Letters
8188:Operations Research Letters
7924:10.1137/1.9781611975482.107
7766:Operations Research Letters
7742:Dantzig, George B. (1963),
7211:Seven Bridges of Königsberg
7183:
7099:The TSP, in particular the
7091:by a randomized algorithm.
6976:Complexity of approximation
6170:times the distance between
5909:{\displaystyle {\sqrt {n}}}
5543:bounded convergence theorem
4301:simulation of an ant colony
4091:{\displaystyle O(n\log(n))}
2901:{\displaystyle c_{ij}>0}
1339:the interpretation is that
635:{\displaystyle c_{ij}>0}
599:{\displaystyle 1,\ldots ,n}
42:travelling salesman problem
10:
10778:
10742:Combinatorial optimization
10705:Traveling Salesman Problem
10682:Traveling Salesman Problem
10282:Introduction to Algorithms
9955:Papadimitriou, Christos H.
9878:10.1016/j.jcss.2015.06.003
9340:Journal of Problem Solving
9312:Journal of Problem Solving
9270:Cognitive Systems Research
7977:Hungarian matrix algorithm
7823:10.1016/j.ejor.2013.07.038
7654:10.1016/j.ejor.2010.09.010
7190:Canadian traveller problem
7109:Journal of Problem Solving
4285:
3595:Other approaches include:
3516:for TSP that runs in time
171:
98:) belongs to the class of
58:combinatorial optimization
18:Traveling salesman problem
10627:SIAM Journal on Computing
10600:10.1137/S0097539796309764
10588:SIAM Journal on Computing
9900:Urban Operations Research
9775:Christofides, N. (1976),
9652:10.1017/s0305004100034095
9368:10.1007/s10071-011-0463-9
9171:10.1007/s00426-017-0881-7
8510:10.1112/s0025579300000784
8393:Larson & Odoni (1981)
8234:10.1609/icaps.v23i1.13539
8200:10.1016/j.orl.2004.04.001
8165:10.1007/s10489-006-0018-y
8016:; McGeoch, L. A. (1997).
7788:10.1016/j.orl.2017.04.010
7251:Snow plow routing problem
6733:{\displaystyle L_{n}^{*}}
4355:
4319:deposited by other ants.
4182:-opt method. Whereas the
4146:other possibilities: of 2
4119:is a special case of the
3990:The pairwise exchange or
3453:Held–Karp algorithm
3384:Devising "suboptimal" or
1815:{\displaystyle x_{ij}=0,}
1673:{\displaystyle x_{ij}=1.}
530:manufacturing; see e.g.,
409:undirected weighted graph
407:TSP can be modeled as an
143:, and the manufacture of
10699:University of Heidelberg
10026:; R. Weismantel (eds.).
8523:Fiechter, C.-N. (1994).
8096:10.1007/0-306-48213-4_10
7990:"Optimal Tour of Sweden"
7498:10.1016/j.hm.2020.04.003
7261:
7200:Route inspection problem
6928:Computational complexity
5224:geometric measure theory
4811:Asymmetric path weights
4256:river formation dynamics
4158:The most popular of the
4131:mutually disjoint edges.
3949:{\displaystyle O(n^{3})}
3843:approximation algorithms
3703:multi-fragment algorithm
3699:approximation algorithms
2060:{\displaystyle x_{ij}=0}
2005:where the constant term
955:{\displaystyle x_{ij}=0}
489:Hamiltonian path problem
485:computational complexity
478:Hamiltonian path problem
435:Asymmetric and symmetric
415:, paths are the graph's
343:showed in 1972 that the
10663:Walshaw, Chris (2001),
10654:Walshaw, Chris (2000),
10374:Reading: Addison-Wesley
10165:10.1126/science.7973651
9742:10.1145/1109557.1109627
8817:10.1145/3357713.3384233
8759:10.1145/3188745.3188824
8654:25 October 2007 at the
7754:, sixth printing, 1974.
7688:in Wall street Journal"
7605:10.1145/3406325.3451009
7339:Graph Theory, 1736â1936
7231:Vehicle routing problem
4901:Symmetric path weights
4781:Conversion to symmetric
4734:time; this is called a
4567:in the original graph.
4464:The edges then build a
4293:Artificial intelligence
4282:Ant colony optimization
4252:ant colony optimization
4117:LinâKernighan heuristic
4102:vehicle routing problem
4004:-opt method. The label
3712:Constructive heuristics
3683:Applegate et al. (2006)
3633:Applegate et al. (2006)
1399:is visited before city
470:complete weighted graph
166:optimal control problem
77:vehicle routing problem
10712:TSP visualization tool
10690:University of Waterloo
10536:Psychological Research
10254:10.1287/ijoc.1060.0204
10086:10.1239/aap/1427814579
9325:10.7771/1932-6246.1090
9159:Psychological Research
9086:Memory & Cognition
9058:10.7771/1932-6246.1090
8980:Memory & Cognition
8957:10.7771/1932-6246.1004
8600:Bertsimas, Dimitris J.
8582:10.1287/opre.18.6.1138
8381:Allender et al. (2007)
8023:. In Aarts, E. H. L.;
7918:. pp. 1783â1793.
7887:Held & Karp (1962)
7384:Lawler, E. L. (1985).
7085:
7038:
6915:
6850:
6790:
6734:
6696:
6587:
6462:
6409:
6382:
6354:
6305:
6231:
6197:and the closest point
6191:
6164:
6144:
6091:
6059:
6026:
5996:
5942:
5910:
5886:
5860:
5805:
5759:
5733:
5679:
5642:follow from bounds on
5636:
5635:{\displaystyle \beta }
5616:
5535:
5484:
5483:{\displaystyle \beta }
5459:
5385:
5353:
5314:
5294:
5208:
5168:
4725:
4549:
4548:{\displaystyle d_{AB}}
4454:
4347:
4339:
4227:Randomized improvement
4209:evolutionary computing
4092:
4044:
3987:
3950:
3886:
3830:
3822:
3803:constructive heuristic
3776:
3721:
3612:
3586:
3546:
3509:
3495:
3434:
3347:
3147:
3061:
2990:
2957:
2902:
2863:
2761:
2542:
2455:
2309:
2276:
2230:
2210:
2187:
2167:
2147:
2118:
2117:{\displaystyle u_{i}.}
2088:
2061:
2025:
1996:
1943:
1851:
1850:{\displaystyle n(n-1)}
1816:
1777:
1733:
1674:
1638:
1587:
1565:
1543:
1520:
1500:
1473:
1446:
1445:{\displaystyle x_{ij}}
1416:
1393:
1373:
1331:
1310:
1283:
1245:
1244:{\displaystyle x_{ij}}
1199:
1158:
1134:
1089:
1051:
1027:
979:
956:
920:
868:
834:
801:
762:
676:
656:
636:
600:
569:integer linear program
404:
381:developed the program
276:integer linear program
229:
197:William Rowan Hamilton
192:
191:William Rowan Hamilton
37:
10548:10.1007/s004260000031
10265:Leiserson, Charles E.
9700:10.1145/321105.321111
9603:10.1145/290179.290180
8446:Arlotto, Alessandro;
7138:Physarum polycephalum
7086:
7039:
6916:
6851:
6791:
6735:
6697:
6588:
6463:
6410:
6408:{\displaystyle X_{0}}
6383:
6355:
6306:
6232:
6192:
6190:{\displaystyle X_{0}}
6165:
6145:
6092:
6060:
6027:
5997:
5943:
5911:
5887:
5861:
5806:
5760:
5734:
5680:
5637:
5617:
5536:
5485:
5460:
5386:
5354:
5315:
5295:
5209:
5169:
4744:Joseph S. B. Mitchell
4726:
4550:
4519:printed circuit board
4498:or city-block metric.
4455:
4345:
4333:
4325:global trail updating
4201:LinâKernighanâJohnson
4127:Given a tour, delete
4093:
4045:
3985:
3951:
3887:
3828:
3820:
3777:
3719:
3610:
3587:
3547:
3507:
3496:
3435:
3433:{\displaystyle O(n!)}
3348:
3115:
3029:
2958:
2937:
2903:
2864:
2762:
2510:
2423:
2277:
2256:
2231:
2211:
2188:
2168:
2148:
2146:{\displaystyle u_{i}}
2119:
2089:
2087:{\displaystyle u_{j}}
2062:
2026:
1997:
1944:
1852:
1817:
1778:
1734:
1675:
1639:
1588:
1566:
1564:{\displaystyle \geq }
1544:
1521:
1501:
1499:{\displaystyle u_{i}}
1474:
1472:{\displaystyle u_{i}}
1447:
1417:
1394:
1374:
1332:
1311:
1309:{\displaystyle u_{i}}
1284:
1246:
1200:
1159:
1102:
1090:
1052:
995:
980:
957:
921:
869:
802:
781:
763:
677:
657:
637:
601:
533:U.S. patent 7,054,798
524:cutting stock problem
402:
323:minimum spanning tree
268:Delbert Ray Fulkerson
221:
190:
35:
10732:NP-complete problems
10610:. pp. 540â550.
10329:10.1287/opre.2.4.393
10042:Upravlyaemye Sistemy
10016:Schrijver, Alexander
9726:, pp. 641â648,
8716:Upravlyaemye Sistemy
8618:10.1287/moor.16.1.72
8556:Steinerberger (2015)
8369:Papadimitriou (1977)
8143:Applied Intelligence
7866:10.1287/opre.2.4.393
7722:, Mineola, NY: Dover
7476:Historia Mathematica
7105:cognitive psychology
7055:
7022:
6874:
6806:
6744:
6712:
6609:
6478:
6419:
6392:
6364:
6321:
6247:
6201:
6174:
6154:
6111:
6072:
6036:
6006:
5955:
5920:
5896:
5870:
5824:
5769:
5743:
5696:
5646:
5626:
5549:
5494:
5474:
5404:
5363:
5352:{\displaystyle ^{2}}
5324:
5304:
5258:
5178:
5105:
4649:
4630:In general, for any
4601:symbolic computation
4529:
4402:
4264:cross entropy method
4058:
4043:{\displaystyle O(n)}
4025:
3924:
3885:{\displaystyle O(n)}
3867:
3847:intractable problems
3741:
3665:Princeton University
3641:cutting-plane method
3560:
3520:
3459:
3412:
3386:heuristic algorithms
3369:Computing a solution
2923:
2876:
2790:
2246:
2220:
2197:
2177:
2157:
2130:
2098:
2071:
2035:
2009:
1953:
1864:
1826:
1787:
1747:
1687:
1648:
1602:
1586:{\displaystyle >}
1577:
1555:
1530:
1510:
1483:
1479:variables by making
1456:
1426:
1403:
1383:
1343:
1321:
1293:
1255:
1225:
1168:
1099:
1061:
992:
966:
930:
881:
778:
689:
666:
646:
610:
578:
487:of the problem; see
351:, which implies the
241:Princeton University
44:, also known as the
10382:1989gaso.book.....G
10317:Operations Research
10147:1994Sci...266.1021A
10078:2013arXiv1311.6338S
10008:10.1287/moor.18.1.1
9990:Yannakakis, Mihalis
9644:1959PCPS...55..299B
9432:2013arXiv1303.4969J
9226:2017Heliy...300461K
8694:Christofides (1976)
8570:Operations Research
8277:1997BiSys..43...73D
8128:10.1109/SWAT.1974.4
7165:Travelling Salesman
7128:Natural computation
7001:triangle inequality
6970:triangle inequality
6966:Euclidean distances
6891:
6823:
6770:
6729:
6634:
6503:
6381:{\displaystyle n/2}
6346:
6272:
6136:
5972:
5715:
5671:
5596:
5511:
5423:
5380:
4902:
4812:
4555:is replaced by the
4381:triangle inequality
4370:triangle inequality
4244:simulated annealing
3896:triangle inequality
3821:Creating a matching
3796:dynamic programming
3679:Concorde TSP Solver
3674:Concorde TSP Solver
3623:Implementations of
3449:dynamic programming
3358:subtour elimination
2832: to city
2024:{\displaystyle n-1}
1857:linear constraints
1221:In addition to the
731: to city
294:, J.H. Halton, and
66:operations research
10580:Mitchell, J. S. B.
10511:10.3758/BF03213088
10182:on 6 February 2005
9590:Journal of the ACM
9099:10.3758/bf03196857
9002:10.3758/bf03194380
8911:10.3758/BF03213088
8596:Goemans, Michel X.
8529:Disc. Applied Math
8474:10.1214/15-AAP1142
8448:Steele, J. Michael
7589:, pp. 32â45,
7548:(8 October 2020).
7081:
7034:
6911:
6877:
6846:
6809:
6786:
6756:
6730:
6715:
6692:
6673:
6658:
6620:
6583:
6571:
6542:
6527:
6489:
6458:
6405:
6378:
6350:
6332:
6301:
6289:
6258:
6227:
6187:
6160:
6140:
6122:
6107:By observing that
6087:
6055:
6022:
5992:
5958:
5938:
5906:
5882:
5856:
5801:
5755:
5729:
5701:
5675:
5657:
5632:
5612:
5582:
5573:
5531:
5497:
5480:
5455:
5409:
5393:Euclidean distance
5381:
5366:
5349:
5310:
5290:
5234:be contained in a
5204:
5164:
4900:
4810:
4721:
4589:Euclidean distance
4575:For points in the
4545:
4496:Manhattan distance
4481:Euclidean distance
4470:distance functions
4450:
4348:
4340:
4260:swarm intelligence
4240:genetic algorithms
4088:
4040:
3988:
3946:
3882:
3831:
3823:
3772:
3722:
3657:linear programming
3655:in 1954, based on
3618:linear programming
3613:
3582:
3542:
3510:
3491:
3430:
3406:brute-force search
3343:
3341:
3245:
3216:
2898:
2859:
2854:
2757:
2755:
2226:
2209:{\displaystyle 1,}
2206:
2186:{\displaystyle 1.}
2183:
2163:
2143:
2114:
2084:
2057:
2021:
1992:
1939:
1847:
1812:
1773:
1729:
1670:
1634:
1583:
1561:
1542:{\displaystyle i.}
1539:
1516:
1496:
1469:
1442:
1415:{\displaystyle j.}
1412:
1389:
1369:
1327:
1306:
1279:
1241:
1195:
1154:
1085:
1047:
978:{\displaystyle 2n}
975:
952:
916:
864:
758:
753:
672:
652:
632:
596:
405:
395:As a graph problem
278:and developed the
193:
161:similarity measure
113:(but no more than
38:
10488:978-0-471-90413-7
10446:978-0-387-44459-8
10391:978-0-201-15767-3
10364:978-0-7167-1044-8
10292:978-0-262-03384-8
10269:Rivest, Ronald L.
10261:Cormen, Thomas H.
10229:978-0-691-15270-7
9909:978-0-13-939447-8
9902:, Prentice-Hall,
9751:978-0-89871-605-4
9570:10.1137/070697926
9529:978-0-691-12993-8
9414:Natural Computing
8826:978-1-4503-6979-4
8768:978-1-4503-5559-9
8427:(161â163): 1983.
8105:978-0-387-44459-8
7933:978-1-61197-548-2
7614:978-1-4503-8053-9
7397:978-0-471-90413-7
7289:10.1002/net.10114
7236:Graph exploration
6903:
6835:
6781:
6687:
6672:
6657:
6578:
6570:
6556:
6541:
6526:
6296:
6288:
6163:{\displaystyle n}
6053:
6020:
5984:
5936:
5904:
5848:
5721:
5720:
5610:
5558:
5523:
5441:
5429:
5428:
5313:{\displaystyle n}
5236:rectifiable curve
5218:Analyst's problem
5089:
5088:
4879:
4878:
4746:were awarded the
4695:
4309:ant colony system
3978:Pairwise exchange
3857:, we can find an
3653:Selmer M. Johnson
3218:
3201:
2850:
2833:
2825:
2229:{\displaystyle 1}
2166:{\displaystyle 1}
2126:The way that the
1949:for all distinct
1683:Merely requiring
1519:{\displaystyle 1}
1392:{\displaystyle i}
1330:{\displaystyle 1}
1289:a dummy variable
985:linear equations
749:
732:
724:
675:{\displaystyle j}
655:{\displaystyle i}
474:Hamiltonian cycle
345:Hamiltonian cycle
292:Jillian Beardwood
272:Selmer M. Johnson
225:messenger problem
209:Hamiltonian cycle
111:superpolynomially
81:ring star problem
16:(Redirected from
10769:
10747:Graph algorithms
10737:NP-hard problems
10670:
10659:
10650:
10621:
10619:
10602:
10594:(4): 1298â1309,
10575:
10530:
10513:
10492:
10471:
10469:
10450:
10429:
10419:
10394:
10368:
10347:
10296:
10275:(31 July 2009).
10256:
10233:
10209:
10200:
10183:
10181:
10175:, archived from
10158:
10141:(5187): 1021â4,
10132:
10124:Adleman, Leonard
10109:
10096:
10071:
10049:
10036:
10034:
10010:
9983:
9974:
9949:
9920:
9889:
9880:
9871:
9862:(8): 1665â1677,
9849:
9848:, pp. 56â65
9839:
9811:
9802:
9780:
9770:
9735:
9718:Karpinski, Marek
9711:
9702:
9680:
9670:
9621:
9586:
9572:
9563:
9554:(5): 1987â2006,
9543:
9532:
9500:
9492:
9486:
9485:
9483:
9481:
9466:
9460:
9459:
9457:
9455:
9441:
9435:
9434:
9425:
9411:
9402:
9396:
9395:
9356:Animal Cognition
9351:
9345:
9336:
9330:
9328:
9327:
9303:
9294:
9293:
9264:
9258:
9257:
9247:
9237:
9205:
9199:
9198:
9154:
9148:
9147:
9138:(5): 1059â1071.
9126:
9120:
9119:
9101:
9077:
9071:
9070:
9060:
9036:
9030:
9029:
8995:
8975:
8969:
8968:
8950:
8930:
8924:
8922:
8913:
8893:
8887:
8881:
8875:
8872:Serdyukov (1984)
8869:
8863:
8857:
8851:
8845:
8839:
8838:
8810:
8787:
8781:
8780:
8742:
8736:
8730:
8724:
8723:
8713:
8703:
8697:
8691:
8685:
8679:
8673:
8672:
8664:
8658:
8646:
8640:
8639:
8628:
8622:
8621:
8592:
8586:
8585:
8576:(6): 1138â1162.
8565:
8559:
8553:
8547:
8546:
8544:
8520:
8514:
8513:
8491:
8485:
8484:
8467:
8458:(4): 2141â2168,
8443:
8437:
8436:
8414:
8408:
8402:
8396:
8390:
8384:
8378:
8372:
8366:
8360:
8359:
8321:
8315:
8314:
8288:
8260:
8254:
8253:
8219:
8210:
8204:
8203:
8183:
8177:
8176:
8158:
8138:
8132:
8131:
8115:
8109:
8108:
8089:
8073:
8067:
8065:
8063:
8039:
8033:
8032:
8022:
8010:
8001:
8000:
7998:
7996:
7985:
7979:
7969:
7964:
7958:
7952:
7946:
7945:
7907:
7901:
7898:Woeginger (2003)
7895:
7889:
7876:
7870:
7869:
7849:
7843:
7833:
7827:
7826:
7806:
7800:
7799:
7781:
7761:
7755:
7740:
7734:
7731:
7725:
7723:
7715:
7709:
7708:
7701:
7695:
7694:
7692:
7680:
7674:
7672:
7635:
7626:
7625:
7598:
7571:
7565:
7564:
7562:
7560:
7546:Klarreich, Erica
7542:
7536:
7535:
7533:
7531:
7516:
7510:
7509:
7491:
7471:
7460:
7454:
7443:
7440:Schrijver (2005)
7436:
7430:
7429:
7427:
7425:
7419:
7408:
7402:
7401:
7381:
7360:
7353:Schrijver (2005)
7349:
7343:
7334:
7328:
7318:
7312:
7307:
7301:
7300:
7272:
7221:Subway Challenge
7152:printed circuits
7116:animal cognition
7114:A 2011 study in
7090:
7088:
7087:
7082:
7077:
7043:
7041:
7040:
7035:
7017:
6946:decision problem
6942:function problem
6938:complexity class
6920:
6918:
6917:
6912:
6904:
6899:
6890:
6885:
6863:Antonia J. Jones
6855:
6853:
6852:
6847:
6836:
6831:
6822:
6817:
6795:
6793:
6792:
6787:
6782:
6777:
6775:
6769:
6764:
6739:
6737:
6736:
6731:
6728:
6723:
6701:
6699:
6698:
6693:
6688:
6683:
6681:
6680:
6674:
6665:
6659:
6650:
6647:
6646:
6633:
6628:
6616:
6592:
6590:
6589:
6584:
6579:
6574:
6572:
6563:
6557:
6552:
6550:
6549:
6543:
6534:
6528:
6519:
6516:
6515:
6502:
6497:
6485:
6467:
6465:
6464:
6459:
6457:
6456:
6444:
6443:
6431:
6430:
6414:
6412:
6411:
6406:
6404:
6403:
6387:
6385:
6384:
6379:
6374:
6360:is greater than
6359:
6357:
6356:
6351:
6345:
6340:
6328:
6310:
6308:
6307:
6302:
6297:
6292:
6290:
6281:
6271:
6266:
6254:
6236:
6234:
6233:
6228:
6226:
6225:
6213:
6212:
6196:
6194:
6193:
6188:
6186:
6185:
6169:
6167:
6166:
6161:
6150:is greater than
6149:
6147:
6146:
6141:
6135:
6130:
6118:
6096:
6094:
6093:
6088:
6064:
6062:
6061:
6056:
6054:
6049:
6031:
6029:
6028:
6023:
6021:
6016:
6001:
5999:
5998:
5993:
5985:
5977:
5971:
5966:
5947:
5945:
5944:
5939:
5937:
5932:
5930:
5916:slices of width
5915:
5913:
5912:
5907:
5905:
5900:
5891:
5889:
5888:
5883:
5866:, and therefore
5865:
5863:
5862:
5857:
5849:
5844:
5836:
5835:
5810:
5808:
5807:
5802:
5800:
5799:
5781:
5780:
5764:
5762:
5761:
5756:
5738:
5736:
5735:
5730:
5722:
5716:
5714:
5709:
5700:
5684:
5682:
5681:
5676:
5670:
5665:
5653:
5641:
5639:
5638:
5633:
5621:
5619:
5618:
5613:
5611:
5606:
5604:
5595:
5590:
5578:
5572:
5540:
5538:
5537:
5532:
5524:
5519:
5510:
5505:
5489:
5487:
5486:
5481:
5464:
5462:
5461:
5456:
5442:
5439:
5430:
5424:
5422:
5417:
5408:
5390:
5388:
5387:
5382:
5379:
5374:
5358:
5356:
5355:
5350:
5348:
5347:
5319:
5317:
5316:
5311:
5299:
5297:
5296:
5291:
5289:
5288:
5270:
5269:
5213:
5211:
5210:
5205:
5203:
5173:
5171:
5170:
5165:
5163:
5156:
5139:
5122:
4903:
4899:
4813:
4809:
4730:
4728:
4727:
4722:
4720:
4719:
4715:
4714:
4713:
4712:
4711:
4696:
4691:
4585:polygonalization
4554:
4552:
4551:
4546:
4544:
4543:
4459:
4457:
4456:
4451:
4449:
4448:
4433:
4432:
4417:
4416:
4364:, also known as
4317:trail pheromones
4145:
4099:
4097:
4095:
4094:
4089:
4051:
4049:
4047:
4046:
4041:
4017:greedy algorithm
3955:
3953:
3952:
3947:
3942:
3941:
3893:
3891:
3889:
3888:
3883:
3839:perfect matching
3792:monotone polygon
3781:
3779:
3778:
3773:
3768:
3760:
3730:greedy algorithm
3625:branch-and-bound
3601:branch-and-bound
3591:
3589:
3588:
3583:
3578:
3577:
3551:
3549:
3548:
3543:
3538:
3537:
3500:
3498:
3497:
3492:
3487:
3486:
3477:
3476:
3439:
3437:
3436:
3431:
3396:Exact algorithms
3379:exact algorithms
3352:
3350:
3349:
3344:
3342:
3332:
3324:
3285:
3277:
3269:
3261:
3260:
3259:
3258:
3244:
3215:
3197:
3168:
3160:
3159:
3146:
3141:
3111:
3082:
3074:
3073:
3060:
3055:
3025:
3022:
3021:
3016:
3015:
3003:
3002:
2989:
2984:
2956:
2951:
2907:
2905:
2904:
2899:
2891:
2890:
2868:
2866:
2865:
2860:
2858:
2857:
2851:
2848:
2834:
2831:
2826:
2823:
2805:
2804:
2766:
2764:
2763:
2758:
2756:
2733:
2726:
2721:
2720:
2676:
2671:
2670:
2630:
2619:
2618:
2606:
2605:
2567:
2560:
2555:
2554:
2541:
2536:
2480:
2473:
2468:
2467:
2454:
2449:
2387:
2366:
2361:
2360:
2345:
2344:
2335:
2334:
2322:
2321:
2308:
2303:
2275:
2270:
2235:
2233:
2232:
2227:
2215:
2213:
2212:
2207:
2192:
2190:
2189:
2184:
2172:
2170:
2169:
2164:
2152:
2150:
2149:
2144:
2142:
2141:
2123:
2121:
2120:
2115:
2110:
2109:
2093:
2091:
2090:
2085:
2083:
2082:
2066:
2064:
2063:
2058:
2050:
2049:
2030:
2028:
2027:
2022:
2001:
1999:
1998:
1993:
1948:
1946:
1945:
1940:
1935:
1934:
1889:
1888:
1876:
1875:
1856:
1854:
1853:
1848:
1821:
1819:
1818:
1813:
1802:
1801:
1782:
1780:
1779:
1774:
1772:
1771:
1759:
1758:
1738:
1736:
1735:
1730:
1728:
1727:
1712:
1711:
1699:
1698:
1679:
1677:
1676:
1671:
1663:
1662:
1643:
1641:
1640:
1635:
1627:
1626:
1614:
1613:
1594:
1592:
1590:
1589:
1584:
1570:
1568:
1567:
1562:
1548:
1546:
1545:
1540:
1525:
1523:
1522:
1517:
1505:
1503:
1502:
1497:
1495:
1494:
1478:
1476:
1475:
1470:
1468:
1467:
1451:
1449:
1448:
1443:
1441:
1440:
1421:
1419:
1418:
1413:
1398:
1396:
1395:
1390:
1378:
1376:
1375:
1370:
1368:
1367:
1355:
1354:
1338:
1336:
1334:
1333:
1328:
1315:
1313:
1312:
1307:
1305:
1304:
1288:
1286:
1285:
1280:
1250:
1248:
1247:
1242:
1240:
1239:
1204:
1202:
1201:
1196:
1163:
1161:
1160:
1155:
1147:
1146:
1133:
1128:
1094:
1092:
1091:
1086:
1056:
1054:
1053:
1048:
1040:
1039:
1026:
1021:
984:
982:
981:
976:
961:
959:
958:
953:
945:
944:
925:
923:
922:
917:
915:
914:
899:
898:
873:
871:
870:
865:
860:
859:
847:
846:
833:
828:
800:
795:
767:
765:
764:
759:
757:
756:
750:
747:
733:
730:
725:
722:
704:
703:
681:
679:
678:
673:
661:
659:
658:
653:
641:
639:
638:
633:
625:
624:
605:
603:
602:
597:
535:
459:Related problems
445:undirected graph
360:branch-and-bound
311:computer science
285:branch-and-bound
256:RAND Corporation
245:RAND Corporation
233:Merrill M. Flood
130:exact algorithms
21:
10777:
10776:
10772:
10771:
10770:
10768:
10767:
10766:
10717:
10716:
10686:Wayback Machine
10678:
10673:
10639:10.1137/0206041
10489:
10467:
10447:
10439:. Springer US.
10392:
10365:
10293:
10273:Stein, Clifford
10230:
10179:
10130:
10118:
10116:Further reading
10113:
10102:Woeginger, G.J.
10032:
9939:10.1137/1033004
9910:
9837:10.1137/0110015
9752:
9733:10.1.1.430.2224
9716:Berman, Piotr;
9584:
9561:10.1.1.167.5495
9547:SIAM J. Comput.
9541:
9530:
9509:
9504:
9503:
9493:
9489:
9479:
9477:
9467:
9463:
9453:
9451:
9443:
9442:
9438:
9409:
9403:
9399:
9352:
9348:
9337:
9333:
9304:
9297:
9265:
9261:
9206:
9202:
9165:(5): 997â1009.
9155:
9151:
9127:
9123:
9078:
9074:
9037:
9033:
8976:
8972:
8948:10.1.1.360.9763
8931:
8927:
8894:
8890:
8882:
8878:
8870:
8866:
8858:
8854:
8846:
8842:
8827:
8788:
8784:
8769:
8743:
8739:
8731:
8727:
8711:
8704:
8700:
8692:
8688:
8680:
8676:
8665:
8661:
8656:Wayback Machine
8647:
8643:
8630:
8629:
8625:
8593:
8589:
8566:
8562:
8554:
8550:
8521:
8517:
8492:
8488:
8444:
8440:
8415:
8411:
8403:
8399:
8391:
8387:
8379:
8375:
8367:
8363:
8340:10.2307/2313333
8322:
8318:
8261:
8257:
8217:
8211:
8207:
8184:
8180:
8139:
8135:
8116:
8112:
8106:
8074:
8070:
8040:
8036:
8020:
8011:
8004:
7994:
7992:
7986:
7982:
7967:
7965:
7961:
7953:
7949:
7934:
7908:
7904:
7896:
7892:
7877:
7873:
7850:
7846:
7834:
7830:
7807:
7803:
7762:
7758:
7741:
7737:
7732:
7728:
7716:
7712:
7702:
7698:
7690:
7682:
7681:
7677:
7636:
7629:
7615:
7575:Karlin, Anna R.
7572:
7568:
7558:
7556:
7554:Quanta Magazine
7543:
7539:
7529:
7527:
7517:
7513:
7472:
7463:
7455:
7446:
7437:
7433:
7423:
7421:
7417:
7409:
7405:
7398:
7382:
7363:
7350:
7346:
7335:
7331:
7325:commis-voyageur
7319:
7315:
7308:
7304:
7273:
7269:
7264:
7206:Set TSP problem
7195:Exact algorithm
7186:
7177:Robert A. Bosch
7160:
7158:Popular culture
7147:
7130:
7097:
7073:
7056:
7053:
7052:
7023:
7020:
7019:
7011:
6992:-complete, and
6978:
6930:
6898:
6886:
6881:
6875:
6872:
6871:
6830:
6818:
6813:
6807:
6804:
6803:
6776:
6771:
6765:
6760:
6745:
6742:
6741:
6740:, and thus for
6724:
6719:
6713:
6710:
6709:
6682:
6676:
6675:
6663:
6648:
6642:
6641:
6629:
6624:
6612:
6610:
6607:
6606:
6573:
6561:
6551:
6545:
6544:
6532:
6517:
6511:
6510:
6498:
6493:
6481:
6479:
6476:
6475:
6452:
6448:
6439:
6435:
6426:
6422:
6420:
6417:
6416:
6399:
6395:
6393:
6390:
6389:
6370:
6365:
6362:
6361:
6341:
6336:
6324:
6322:
6319:
6318:
6291:
6279:
6267:
6262:
6250:
6248:
6245:
6244:
6221:
6217:
6208:
6204:
6202:
6199:
6198:
6181:
6177:
6175:
6172:
6171:
6155:
6152:
6151:
6131:
6126:
6114:
6112:
6109:
6108:
6104:
6073:
6070:
6069:
6048:
6037:
6034:
6033:
6015:
6007:
6004:
6003:
5976:
5967:
5962:
5956:
5953:
5952:
5931:
5926:
5921:
5918:
5917:
5899:
5897:
5894:
5893:
5871:
5868:
5867:
5843:
5831:
5827:
5825:
5822:
5821:
5817:
5795:
5791:
5776:
5772:
5770:
5767:
5766:
5744:
5741:
5740:
5710:
5705:
5699:
5697:
5694:
5693:
5666:
5661:
5649:
5647:
5644:
5643:
5627:
5624:
5623:
5605:
5600:
5591:
5586:
5574:
5562:
5550:
5547:
5546:
5518:
5506:
5501:
5495:
5492:
5491:
5475:
5472:
5471:
5438:
5418:
5413:
5407:
5405:
5402:
5401:
5375:
5370:
5364:
5361:
5360:
5343:
5339:
5325:
5322:
5321:
5305:
5302:
5301:
5284:
5280:
5265:
5261:
5259:
5256:
5255:
5252:
5232:Euclidean space
5220:
5181:
5179:
5176:
5175:
5149:
5132:
5115:
5108:
5106:
5103:
5102:
4783:
4759:
4701:
4697:
4690:
4680:
4676:
4660:
4656:
4655:
4650:
4647:
4646:
4597:sum of radicals
4577:Euclidean plane
4573:
4559:length between
4536:
4532:
4530:
4527:
4526:
4441:
4437:
4425:
4421:
4409:
4405:
4403:
4400:
4399:
4379:to satisfy the
4358:
4353:
4290:
4284:
4272:
4229:
4196:Brian Kernighan
4176:
4139:
4113:
4059:
4056:
4055:
4053:
4026:
4023:
4022:
4020:
3980:
3937:
3933:
3925:
3922:
3921:
3868:
3865:
3864:
3862:
3815:
3764:
3756:
3742:
3739:
3738:
3714:
3691:
3669:Alpha processor
3661:Rice University
3573:
3569:
3561:
3558:
3557:
3554:exact algorithm
3533:
3529:
3521:
3518:
3517:
3514:exact algorithm
3482:
3478:
3472:
3468:
3460:
3457:
3456:
3413:
3410:
3409:
3398:
3371:
3340:
3339:
3328:
3320:
3284:
3273:
3265:
3251:
3247:
3246:
3222:
3217:
3205:
3195:
3194:
3167:
3152:
3148:
3142:
3119:
3109:
3108:
3081:
3066:
3062:
3056:
3033:
3023:
3020:
3008:
3004:
2995:
2991:
2985:
2962:
2952:
2941:
2933:
2926:
2924:
2921:
2920:
2883:
2879:
2877:
2874:
2873:
2853:
2852:
2847:
2845:
2839:
2838:
2830:
2822:
2820:
2810:
2809:
2797:
2793:
2791:
2788:
2787:
2777:
2754:
2753:
2732:
2727:
2725:
2716:
2712:
2703:
2702:
2675:
2663:
2659:
2631:
2629:
2614:
2610:
2601:
2597:
2594:
2593:
2566:
2561:
2559:
2547:
2543:
2537:
2514:
2507:
2506:
2479:
2474:
2472:
2460:
2456:
2450:
2427:
2420:
2419:
2386:
2367:
2365:
2353:
2349:
2346:
2343:
2336:
2327:
2323:
2314:
2310:
2304:
2281:
2271:
2260:
2249:
2247:
2244:
2243:
2221:
2218:
2217:
2198:
2195:
2194:
2178:
2175:
2174:
2158:
2155:
2154:
2137:
2133:
2131:
2128:
2127:
2105:
2101:
2099:
2096:
2095:
2078:
2074:
2072:
2069:
2068:
2042:
2038:
2036:
2033:
2032:
2010:
2007:
2006:
1954:
1951:
1950:
1927:
1923:
1884:
1880:
1871:
1867:
1865:
1862:
1861:
1827:
1824:
1823:
1794:
1790:
1788:
1785:
1784:
1767:
1763:
1754:
1750:
1748:
1745:
1744:
1720:
1716:
1707:
1703:
1694:
1690:
1688:
1685:
1684:
1655:
1651:
1649:
1646:
1645:
1622:
1618:
1609:
1605:
1603:
1600:
1599:
1578:
1575:
1574:
1572:
1556:
1553:
1552:
1531:
1528:
1527:
1511:
1508:
1507:
1490:
1486:
1484:
1481:
1480:
1463:
1459:
1457:
1454:
1453:
1433:
1429:
1427:
1424:
1423:
1404:
1401:
1400:
1384:
1381:
1380:
1363:
1359:
1350:
1346:
1344:
1341:
1340:
1322:
1319:
1318:
1317:
1300:
1296:
1294:
1291:
1290:
1256:
1253:
1252:
1232:
1228:
1226:
1223:
1222:
1219:
1169:
1166:
1165:
1139:
1135:
1129:
1106:
1100:
1097:
1096:
1062:
1059:
1058:
1032:
1028:
1022:
999:
993:
990:
989:
967:
964:
963:
937:
933:
931:
928:
927:
904:
900:
891:
887:
882:
879:
878:
852:
848:
839:
835:
829:
806:
796:
785:
779:
776:
775:
752:
751:
746:
744:
738:
737:
729:
721:
719:
709:
708:
696:
692:
690:
687:
686:
667:
664:
663:
647:
644:
643:
617:
613:
611:
608:
607:
579:
576:
575:
565:
538:distance matrix
531:
508:printed circuit
461:
437:
397:
392:
341:Richard M. Karp
296:John Hammersley
237:Hassler Whitney
174:
60:, important in
28:
23:
22:
15:
12:
11:
5:
10775:
10765:
10764:
10759:
10754:
10749:
10744:
10739:
10734:
10729:
10715:
10714:
10709:
10701:
10692:
10677:
10676:External links
10674:
10672:
10671:
10660:
10651:
10622:
10617:10.1.1.51.8676
10603:
10576:
10531:
10504:(4): 527â539,
10493:
10487:
10472:
10459:Lenstra, J. K.
10455:Johnson, D. S.
10451:
10445:
10430:
10410:(1â3): 81â86.
10395:
10390:
10369:
10363:
10348:
10323:(4): 393â410,
10309:Johnson, S. M.
10301:Dantzig, G. B.
10297:
10291:
10257:
10248:(3): 356â365,
10234:
10228:
10210:
10198:10.1.1.89.9953
10184:
10156:10.1.1.54.2565
10119:
10117:
10114:
10112:
10111:
10098:
10051:
10037:
10024:G.L. Nemhauser
10012:
9985:
9965:(3): 237â244,
9951:
9922:
9908:
9891:
9881:
9851:
9841:
9831:(1): 196â210,
9813:
9800:10.1.1.35.7209
9793:(4): 181â186,
9782:
9772:
9750:
9713:
9682:
9672:
9638:(4): 299â327,
9623:
9597:(5): 753â782,
9578:Arora, Sanjeev
9574:
9534:
9528:
9510:
9508:
9505:
9502:
9501:
9487:
9461:
9436:
9397:
9362:(3): 379â391.
9346:
9331:
9295:
9259:
9220:(11): e00461.
9200:
9149:
9121:
9092:(2): 260â270.
9072:
9031:
8993:10.1.1.12.6117
8986:(2): 215â220.
8970:
8925:
8904:(4): 527â539,
8888:
8876:
8864:
8852:
8840:
8825:
8782:
8767:
8737:
8725:
8718:(in Russian),
8698:
8686:
8674:
8659:
8641:
8623:
8587:
8560:
8548:
8535:(3): 243â267.
8515:
8504:(2): 141â144.
8486:
8438:
8409:
8397:
8385:
8373:
8361:
8334:(9): 977â980.
8316:
8286:10.1.1.54.7734
8255:
8205:
8194:(6): 499â509.
8178:
8156:10.1.1.151.132
8149:(3): 183â195.
8133:
8110:
8104:
8087:10.1.1.24.2386
8068:
8054:(1â3): 81â86.
8034:
8025:Lenstra, J. K.
8014:Johnson, D. S.
8002:
7980:
7959:
7947:
7932:
7902:
7890:
7883:Bellman (1962)
7879:Bellman (1960)
7871:
7860:(4): 393â410.
7844:
7828:
7817:(3): 820â832.
7801:
7772:(4): 323â324.
7756:
7735:
7726:
7710:
7696:
7675:
7648:(3): 427â441,
7627:
7613:
7579:Khuller, Samir
7566:
7537:
7511:
7461:
7444:
7431:
7403:
7396:
7361:
7344:
7329:
7313:
7302:
7283:(3): 177â189.
7266:
7265:
7263:
7260:
7259:
7258:
7253:
7248:
7243:
7238:
7233:
7228:
7226:Tube Challenge
7223:
7218:
7213:
7208:
7203:
7197:
7192:
7185:
7182:
7181:
7180:
7173:
7159:
7156:
7146:
7143:
7129:
7126:
7096:
7093:
7080:
7076:
7072:
7069:
7066:
7063:
7060:
7033:
7030:
7027:
6977:
6974:
6929:
6926:
6925:
6924:
6923:
6922:
6910:
6907:
6902:
6897:
6894:
6889:
6884:
6880:
6859:
6858:
6857:
6856:
6845:
6842:
6839:
6834:
6829:
6826:
6821:
6816:
6812:
6798:
6797:
6785:
6780:
6774:
6768:
6763:
6759:
6755:
6752:
6749:
6727:
6722:
6718:
6705:
6704:
6703:
6702:
6691:
6686:
6679:
6671:
6668:
6662:
6656:
6653:
6645:
6640:
6637:
6632:
6627:
6623:
6619:
6615:
6601:
6600:
6596:
6595:
6594:
6593:
6582:
6577:
6569:
6566:
6560:
6555:
6548:
6540:
6537:
6531:
6525:
6522:
6514:
6509:
6506:
6501:
6496:
6492:
6488:
6484:
6470:
6469:
6455:
6451:
6447:
6442:
6438:
6434:
6429:
6425:
6402:
6398:
6377:
6373:
6369:
6349:
6344:
6339:
6335:
6331:
6327:
6314:
6313:
6312:
6311:
6300:
6295:
6287:
6284:
6278:
6275:
6270:
6265:
6261:
6257:
6253:
6239:
6238:
6224:
6220:
6216:
6211:
6207:
6184:
6180:
6159:
6139:
6134:
6129:
6125:
6121:
6117:
6103:
6100:
6099:
6098:
6086:
6083:
6080:
6077:
6066:
6052:
6047:
6044:
6041:
6019:
6014:
6011:
5991:
5988:
5983:
5980:
5975:
5970:
5965:
5961:
5949:
5948:in the square.
5935:
5929:
5925:
5903:
5881:
5878:
5875:
5855:
5852:
5847:
5842:
5839:
5834:
5830:
5816:
5813:
5798:
5794:
5790:
5787:
5784:
5779:
5775:
5754:
5751:
5748:
5728:
5725:
5719:
5713:
5708:
5704:
5674:
5669:
5664:
5660:
5656:
5652:
5631:
5609:
5603:
5599:
5594:
5589:
5585:
5581:
5577:
5571:
5568:
5565:
5561:
5557:
5554:
5530:
5527:
5522:
5517:
5514:
5509:
5504:
5500:
5479:
5468:
5467:
5466:
5465:
5454:
5451:
5448:
5445:
5436:
5433:
5427:
5421:
5416:
5412:
5378:
5373:
5369:
5346:
5342:
5338:
5335:
5332:
5329:
5309:
5287:
5283:
5279:
5276:
5273:
5268:
5264:
5251:
5248:
5219:
5216:
5202:
5199:
5196:
5193:
5190:
5187:
5184:
5162:
5159:
5155:
5152:
5148:
5145:
5142:
5138:
5135:
5131:
5128:
5125:
5121:
5118:
5114:
5111:
5091:
5090:
5087:
5086:
5084:
5082:
5080:
5074:
5071:
5068:
5062:
5061:
5059:
5057:
5055:
5052:
5046:
5043:
5037:
5036:
5034:
5032:
5030:
5027:
5024:
5018:
5012:
5011:
5005:
5002:
4999:
4997:
4995:
4993:
4987:
4986:
4983:
4977:
4974:
4972:
4970:
4968:
4962:
4961:
4958:
4955:
4949:
4947:
4945:
4943:
4937:
4936:
4931:
4926:
4921:
4916:
4911:
4906:
4881:
4880:
4877:
4876:
4874:
4871:
4868:
4862:
4861:
4858:
4856:
4853:
4847:
4846:
4843:
4840:
4838:
4832:
4831:
4826:
4821:
4816:
4782:
4779:
4758:
4755:
4732:
4731:
4718:
4710:
4707:
4704:
4700:
4694:
4689:
4686:
4683:
4679:
4675:
4672:
4669:
4666:
4663:
4659:
4654:
4634:> 0, where
4581:simple polygon
4572:
4569:
4542:
4539:
4535:
4515:
4514:
4503:maximum metric
4499:
4484:
4462:
4461:
4447:
4444:
4440:
4436:
4431:
4428:
4424:
4420:
4415:
4412:
4408:
4357:
4354:
4352:
4349:
4286:Main article:
4283:
4280:
4271:
4268:
4228:
4225:
4175:
4174:-opt heuristic
4169:
4156:
4155:
4144: â 2
4136:
4132:
4112:
4106:
4087:
4084:
4081:
4078:
4075:
4072:
4069:
4066:
4063:
4039:
4036:
4033:
4030:
3979:
3976:
3975:
3974:
3971:
3968:
3965:
3945:
3940:
3936:
3932:
3929:
3913:
3912:
3909:
3906:
3903:
3881:
3878:
3875:
3872:
3855:Eulerian graph
3814:
3811:
3771:
3767:
3763:
3759:
3755:
3752:
3749:
3746:
3713:
3710:
3690:
3687:
3645:George Dantzig
3637:
3636:
3629:branch-and-cut
3621:
3605:
3604:
3581:
3576:
3572:
3568:
3565:
3541:
3536:
3532:
3528:
3525:
3490:
3485:
3481:
3475:
3471:
3467:
3464:
3429:
3426:
3423:
3420:
3417:
3397:
3394:
3393:
3392:
3389:
3382:
3370:
3367:
3363:row generation
3354:
3353:
3338:
3335:
3331:
3327:
3323:
3319:
3316:
3313:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3286:
3283:
3280:
3276:
3272:
3268:
3264:
3257:
3254:
3250:
3243:
3240:
3237:
3234:
3231:
3228:
3225:
3221:
3214:
3211:
3208:
3204:
3200:
3198:
3196:
3193:
3190:
3187:
3184:
3181:
3178:
3175:
3172:
3169:
3166:
3163:
3158:
3155:
3151:
3145:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3118:
3114:
3112:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3077:
3072:
3069:
3065:
3059:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3032:
3028:
3026:
3024:
3019:
3014:
3011:
3007:
3001:
2998:
2994:
2988:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2961:
2955:
2950:
2947:
2944:
2940:
2936:
2934:
2932:
2929:
2928:
2897:
2894:
2889:
2886:
2882:
2870:
2869:
2856:
2846:
2844:
2841:
2840:
2837:
2829:
2821:
2819:
2816:
2815:
2813:
2808:
2803:
2800:
2796:
2776:
2773:
2768:
2767:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2724:
2719:
2715:
2711:
2708:
2705:
2704:
2701:
2698:
2695:
2692:
2689:
2686:
2683:
2680:
2677:
2674:
2669:
2666:
2662:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2632:
2628:
2625:
2622:
2617:
2613:
2609:
2604:
2600:
2596:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2558:
2553:
2550:
2546:
2540:
2535:
2532:
2529:
2526:
2523:
2520:
2517:
2513:
2509:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2471:
2466:
2463:
2459:
2453:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2426:
2422:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2370:
2368:
2364:
2359:
2356:
2352:
2348:
2347:
2342:
2339:
2337:
2333:
2330:
2326:
2320:
2317:
2313:
2307:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2280:
2274:
2269:
2266:
2263:
2259:
2255:
2252:
2251:
2225:
2205:
2202:
2182:
2162:
2140:
2136:
2113:
2108:
2104:
2081:
2077:
2056:
2053:
2048:
2045:
2041:
2020:
2017:
2014:
2003:
2002:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1938:
1933:
1930:
1926:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1892:
1887:
1883:
1879:
1874:
1870:
1846:
1843:
1840:
1837:
1834:
1831:
1811:
1808:
1805:
1800:
1797:
1793:
1770:
1766:
1762:
1757:
1753:
1726:
1723:
1719:
1715:
1710:
1706:
1702:
1697:
1693:
1681:
1680:
1669:
1666:
1661:
1658:
1654:
1633:
1630:
1625:
1621:
1617:
1612:
1608:
1582:
1571:) over strict
1560:
1538:
1535:
1515:
1493:
1489:
1466:
1462:
1439:
1436:
1432:
1411:
1408:
1388:
1366:
1362:
1358:
1353:
1349:
1326:
1303:
1299:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1238:
1235:
1231:
1218:
1215:
1206:
1205:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1153:
1150:
1145:
1142:
1138:
1132:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1105:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1046:
1043:
1038:
1035:
1031:
1025:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
998:
974:
971:
951:
948:
943:
940:
936:
913:
910:
907:
903:
897:
894:
890:
886:
875:
874:
863:
858:
855:
851:
845:
842:
838:
832:
827:
824:
821:
818:
815:
812:
809:
805:
799:
794:
791:
788:
784:
769:
768:
755:
745:
743:
740:
739:
736:
728:
720:
718:
715:
714:
712:
707:
702:
699:
695:
671:
651:
631:
628:
623:
620:
616:
595:
592:
589:
586:
583:
564:
561:
560:
559:
551:
544:
541:
516:
500:weighted graph
492:
481:
460:
457:
453:directed graph
449:asymmetric TSP
436:
433:
429:complete graph
396:
393:
391:
388:
365:In the 1990s,
264:George Dantzig
249:Julia Robinson
201:Thomas Kirkman
173:
170:
149:DNA sequencing
26:
9:
6:
4:
3:
2:
10774:
10763:
10760:
10758:
10755:
10753:
10750:
10748:
10745:
10743:
10740:
10738:
10735:
10733:
10730:
10728:
10725:
10724:
10722:
10713:
10710:
10707:
10706:
10702:
10700:
10696:
10693:
10691:
10687:
10683:
10680:
10679:
10668:
10667:
10661:
10657:
10652:
10648:
10644:
10640:
10636:
10632:
10628:
10623:
10618:
10613:
10609:
10604:
10601:
10597:
10593:
10589:
10585:
10581:
10577:
10573:
10569:
10565:
10561:
10557:
10553:
10549:
10545:
10541:
10537:
10532:
10529:
10525:
10521:
10517:
10512:
10507:
10503:
10499:
10494:
10490:
10484:
10480:
10479:
10473:
10466:
10465:
10460:
10456:
10452:
10448:
10442:
10438:
10437:
10431:
10427:
10423:
10418:
10413:
10409:
10405:
10401:
10396:
10393:
10387:
10383:
10379:
10375:
10370:
10366:
10360:
10356:
10355:
10349:
10346:
10342:
10338:
10334:
10330:
10326:
10322:
10318:
10314:
10310:
10306:
10305:Fulkerson, R.
10302:
10298:
10294:
10288:
10284:
10283:
10278:
10274:
10270:
10266:
10262:
10258:
10255:
10251:
10247:
10243:
10239:
10238:Cook, William
10235:
10231:
10225:
10221:
10220:
10215:
10214:Cook, William
10211:
10208:
10204:
10199:
10194:
10190:
10185:
10178:
10174:
10170:
10166:
10162:
10157:
10152:
10148:
10144:
10140:
10136:
10129:
10125:
10121:
10120:
10107:
10103:
10099:
10095:
10091:
10087:
10083:
10079:
10075:
10070:
10065:
10061:
10057:
10052:
10047:
10043:
10038:
10031:
10030:
10025:
10021:
10017:
10013:
10009:
10005:
10001:
9997:
9996:
9991:
9986:
9982:
9978:
9973:
9968:
9964:
9960:
9956:
9952:
9948:
9944:
9940:
9936:
9932:
9928:
9923:
9919:
9915:
9911:
9905:
9901:
9897:
9892:
9887:
9882:
9879:
9875:
9870:
9865:
9861:
9857:
9852:
9847:
9842:
9838:
9834:
9830:
9826:
9822:
9818:
9814:
9810:
9806:
9801:
9796:
9792:
9788:
9783:
9778:
9773:
9769:
9765:
9761:
9757:
9753:
9747:
9743:
9739:
9734:
9729:
9725:
9724:
9719:
9714:
9710:
9706:
9701:
9696:
9692:
9688:
9683:
9678:
9673:
9669:
9665:
9661:
9657:
9653:
9649:
9645:
9641:
9637:
9633:
9629:
9624:
9620:
9616:
9612:
9608:
9604:
9600:
9596:
9592:
9591:
9583:
9579:
9575:
9571:
9567:
9562:
9557:
9553:
9549:
9548:
9540:
9535:
9531:
9525:
9521:
9517:
9512:
9511:
9498:
9497:
9491:
9476:
9472:
9465:
9450:
9446:
9440:
9433:
9429:
9424:
9419:
9415:
9408:
9401:
9393:
9389:
9385:
9381:
9377:
9373:
9369:
9365:
9361:
9357:
9350:
9343:
9341:
9335:
9326:
9321:
9317:
9313:
9309:
9302:
9300:
9291:
9287:
9283:
9279:
9275:
9271:
9263:
9255:
9251:
9246:
9241:
9236:
9231:
9227:
9223:
9219:
9215:
9211:
9204:
9196:
9192:
9188:
9184:
9180:
9176:
9172:
9168:
9164:
9160:
9153:
9145:
9141:
9137:
9133:
9125:
9117:
9113:
9109:
9105:
9100:
9095:
9091:
9087:
9083:
9076:
9068:
9064:
9059:
9054:
9050:
9046:
9042:
9035:
9027:
9023:
9019:
9015:
9011:
9007:
9003:
8999:
8994:
8989:
8985:
8981:
8974:
8966:
8962:
8958:
8954:
8949:
8944:
8940:
8936:
8929:
8921:
8917:
8912:
8907:
8903:
8899:
8892:
8885:
8880:
8873:
8868:
8861:
8856:
8849:
8844:
8836:
8832:
8828:
8822:
8818:
8814:
8809:
8804:
8800:
8796:
8792:
8786:
8778:
8774:
8770:
8764:
8760:
8756:
8752:
8748:
8741:
8734:
8729:
8721:
8717:
8709:
8702:
8695:
8690:
8683:
8678:
8670:
8667:Orponen, P.;
8663:
8657:
8653:
8650:
8645:
8637:
8636:about.att.com
8633:
8627:
8619:
8615:
8611:
8607:
8606:
8601:
8597:
8591:
8583:
8579:
8575:
8571:
8564:
8557:
8552:
8543:
8538:
8534:
8530:
8526:
8519:
8511:
8507:
8503:
8499:
8498:
8490:
8483:
8479:
8475:
8471:
8466:
8461:
8457:
8453:
8449:
8442:
8434:
8430:
8426:
8422:
8421:
8413:
8406:
8401:
8394:
8389:
8382:
8377:
8370:
8365:
8357:
8353:
8349:
8345:
8341:
8337:
8333:
8329:
8328:
8320:
8312:
8308:
8304:
8300:
8296:
8292:
8287:
8282:
8278:
8274:
8270:
8266:
8259:
8251:
8247:
8243:
8239:
8235:
8231:
8227:
8223:
8216:
8209:
8201:
8197:
8193:
8189:
8182:
8174:
8170:
8166:
8162:
8157:
8152:
8148:
8144:
8137:
8129:
8125:
8121:
8114:
8107:
8101:
8097:
8093:
8088:
8083:
8079:
8072:
8062:
8057:
8053:
8049:
8045:
8038:
8030:
8026:
8019:
8015:
8009:
8007:
7991:
7984:
7978:
7974:
7970:
7963:
7956:
7951:
7943:
7939:
7935:
7929:
7925:
7921:
7917:
7913:
7906:
7899:
7894:
7888:
7884:
7880:
7875:
7867:
7863:
7859:
7855:
7848:
7842:
7838:
7832:
7824:
7820:
7816:
7812:
7805:
7797:
7793:
7789:
7785:
7780:
7775:
7771:
7767:
7760:
7753:
7752:0-691-08000-3
7749:
7745:
7739:
7730:
7724:, pp.308-309.
7721:
7714:
7707:
7700:
7689:
7687:
7679:
7671:
7667:
7663:
7659:
7655:
7651:
7647:
7643:
7642:
7634:
7632:
7624:
7620:
7616:
7610:
7606:
7602:
7597:
7592:
7588:
7584:
7580:
7576:
7570:
7555:
7551:
7547:
7541:
7526:
7522:
7515:
7507:
7503:
7499:
7495:
7490:
7485:
7481:
7477:
7470:
7468:
7466:
7458:
7453:
7451:
7449:
7441:
7435:
7416:
7415:
7407:
7399:
7393:
7389:
7388:
7380:
7378:
7376:
7374:
7372:
7370:
7368:
7366:
7358:
7354:
7348:
7341:
7340:
7333:
7326:
7322:
7317:
7311:
7306:
7298:
7294:
7290:
7286:
7282:
7278:
7271:
7267:
7257:
7254:
7252:
7249:
7247:
7244:
7242:
7239:
7237:
7234:
7232:
7229:
7227:
7224:
7222:
7219:
7217:
7214:
7212:
7209:
7207:
7204:
7201:
7198:
7196:
7193:
7191:
7188:
7187:
7178:
7174:
7171:
7167:
7166:
7162:
7161:
7155:
7153:
7142:
7140:
7139:
7135:
7125:
7123:
7122:
7117:
7112:
7110:
7106:
7102:
7092:
7078:
7074:
7067:
7064:
7061:
7050:
7045:
7031:
7028:
7025:
7015:
7010:
7006:
7002:
6997:
6995:
6991:
6987:
6983:
6973:
6971:
6967:
6963:
6959:
6955:
6951:
6947:
6943:
6939:
6935:
6908:
6905:
6900:
6895:
6892:
6887:
6882:
6878:
6870:
6869:
6868:
6867:
6866:
6864:
6843:
6840:
6837:
6832:
6827:
6824:
6819:
6814:
6810:
6802:
6801:
6800:
6799:
6778:
6772:
6766:
6761:
6757:
6753:
6747:
6725:
6720:
6716:
6707:
6706:
6689:
6684:
6669:
6666:
6660:
6654:
6651:
6638:
6630:
6625:
6621:
6605:
6604:
6603:
6602:
6598:
6597:
6580:
6575:
6567:
6564:
6558:
6553:
6538:
6535:
6529:
6523:
6520:
6507:
6499:
6494:
6490:
6474:
6473:
6472:
6471:
6468:, which gives
6453:
6449:
6445:
6440:
6436:
6432:
6427:
6423:
6400:
6396:
6375:
6371:
6367:
6342:
6337:
6333:
6316:
6315:
6298:
6293:
6285:
6282:
6276:
6268:
6263:
6259:
6243:
6242:
6241:
6240:
6222:
6218:
6214:
6209:
6205:
6182:
6178:
6157:
6132:
6127:
6123:
6106:
6105:
6084:
6081:
6078:
6075:
6067:
6050:
6045:
6042:
6039:
6017:
6012:
6009:
5989:
5986:
5981:
5978:
5973:
5968:
5963:
5959:
5950:
5933:
5927:
5923:
5901:
5879:
5876:
5873:
5853:
5850:
5845:
5840:
5837:
5832:
5828:
5819:
5818:
5812:
5796:
5792:
5788:
5785:
5782:
5777:
5773:
5746:
5726:
5717:
5711:
5706:
5702:
5691:
5686:
5667:
5662:
5658:
5629:
5607:
5601:
5592:
5587:
5583:
5563:
5555:
5552:
5544:
5528:
5525:
5520:
5515:
5512:
5507:
5502:
5498:
5477:
5452:
5443:
5434:
5425:
5419:
5414:
5410:
5400:
5399:
5398:
5397:
5396:
5394:
5376:
5371:
5367:
5344:
5336:
5333:
5330:
5307:
5285:
5281:
5277:
5274:
5271:
5266:
5262:
5247:
5245:
5241:
5237:
5233:
5229:
5225:
5215:
5153:
5136:
5119:
5100:
5096:
5085:
5083:
5081:
5079:
5075:
5072:
5069:
5067:
5064:
5063:
5060:
5058:
5056:
5053:
5051:
5047:
5044:
5042:
5039:
5038:
5035:
5033:
5031:
5028:
5025:
5023:
5019:
5017:
5014:
5013:
5010:
5006:
5003:
5000:
4998:
4996:
4994:
4992:
4989:
4988:
4984:
4982:
4978:
4975:
4973:
4971:
4969:
4967:
4964:
4963:
4959:
4956:
4954:
4950:
4948:
4946:
4944:
4942:
4939:
4938:
4935:
4932:
4930:
4927:
4925:
4922:
4920:
4917:
4915:
4912:
4910:
4907:
4905:
4904:
4898:
4897:
4896:
4894:
4890:
4886:
4875:
4872:
4869:
4867:
4864:
4863:
4859:
4857:
4854:
4852:
4849:
4848:
4844:
4841:
4839:
4837:
4834:
4833:
4830:
4827:
4825:
4822:
4820:
4817:
4815:
4814:
4808:
4807:
4806:
4804:
4800:
4796:
4792:
4788:
4778:
4776:
4772:
4768:
4764:
4754:
4751:
4749:
4745:
4741:
4740:Sanjeev Arora
4737:
4716:
4708:
4705:
4702:
4692:
4687:
4681:
4673:
4670:
4667:
4661:
4657:
4652:
4645:
4644:
4643:
4641:
4637:
4633:
4628:
4626:
4622:
4618:
4614:
4610:
4604:
4602:
4598:
4594:
4590:
4586:
4582:
4578:
4568:
4566:
4562:
4558:
4557:shortest path
4540:
4537:
4533:
4522:
4520:
4513:-coordinates.
4512:
4508:
4504:
4500:
4497:
4493:
4489:
4485:
4482:
4478:
4477:
4476:
4473:
4471:
4467:
4445:
4442:
4438:
4434:
4429:
4426:
4422:
4418:
4413:
4410:
4406:
4398:
4397:
4396:
4394:
4390:
4386:
4382:
4378:
4373:
4371:
4367:
4363:
4351:Special cases
4344:
4337:
4332:
4328:
4326:
4320:
4318:
4314:
4310:
4306:
4302:
4298:
4294:
4289:
4279:
4277:
4267:
4265:
4261:
4257:
4253:
4249:
4245:
4241:
4236:
4234:
4224:
4222:
4218:
4217:local minimum
4214:
4210:
4206:
4202:
4197:
4193:
4189:
4185:
4181:
4173:
4168:
4165:
4161:
4153:
4149:
4143:
4137:
4133:
4130:
4126:
4125:
4124:
4122:
4118:
4110:
4105:
4103:
4079:
4073:
4070:
4067:
4061:
4034:
4028:
4018:
4013:
4012:-opt method.
4011:
4007:
4006:LinâKernighan
4003:
3999:
3995:
3994:
3984:
3972:
3969:
3966:
3963:
3962:
3961:
3957:
3938:
3934:
3927:
3919:
3910:
3907:
3904:
3901:
3900:
3899:
3897:
3876:
3870:
3860:
3859:Eulerian tour
3856:
3850:
3848:
3844:
3840:
3836:
3827:
3819:
3810:
3808:
3804:
3799:
3797:
3793:
3789:
3784:
3761:
3753:
3750:
3735:
3731:
3727:
3718:
3709:
3706:
3704:
3700:
3696:
3686:
3684:
3680:
3676:
3675:
3670:
3666:
3662:
3658:
3654:
3650:
3649:Ray Fulkerson
3646:
3642:
3634:
3630:
3626:
3622:
3619:
3615:
3614:
3609:
3602:
3598:
3597:
3596:
3593:
3574:
3570:
3563:
3555:
3534:
3530:
3523:
3515:
3506:
3502:
3483:
3479:
3473:
3469:
3462:
3454:
3450:
3445:
3443:
3424:
3421:
3415:
3407:
3403:
3390:
3387:
3383:
3380:
3376:
3375:
3374:
3366:
3364:
3359:
3336:
3333:
3325:
3317:
3311:
3308:
3305:
3302:
3299:
3293:
3290:
3281:
3278:
3270:
3262:
3255:
3252:
3248:
3241:
3238:
3235:
3232:
3229:
3226:
3223:
3219:
3212:
3209:
3206:
3202:
3199:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3164:
3161:
3156:
3153:
3149:
3143:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3116:
3113:
3105:
3102:
3099:
3096:
3093:
3090:
3087:
3084:
3078:
3075:
3070:
3067:
3063:
3057:
3052:
3049:
3046:
3043:
3040:
3037:
3034:
3030:
3027:
3017:
3012:
3009:
3005:
2999:
2996:
2992:
2986:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2959:
2953:
2948:
2945:
2942:
2938:
2935:
2919:
2918:
2917:
2915:
2911:
2895:
2892:
2887:
2884:
2880:
2842:
2835:
2827:
2817:
2811:
2806:
2801:
2798:
2794:
2786:
2785:
2784:
2782:
2772:
2750:
2747:
2744:
2741:
2738:
2735:
2729:
2722:
2717:
2713:
2709:
2706:
2699:
2696:
2693:
2690:
2687:
2684:
2681:
2678:
2667:
2664:
2660:
2656:
2653:
2644:
2641:
2638:
2633:
2626:
2623:
2620:
2615:
2611:
2607:
2602:
2598:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2563:
2556:
2551:
2548:
2544:
2538:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2511:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2476:
2469:
2464:
2461:
2457:
2451:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2424:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2380:
2377:
2374:
2369:
2362:
2357:
2354:
2350:
2340:
2338:
2331:
2328:
2324:
2318:
2315:
2311:
2305:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2278:
2272:
2267:
2264:
2261:
2257:
2242:
2241:
2240:
2237:
2223:
2203:
2200:
2180:
2160:
2138:
2134:
2124:
2111:
2106:
2102:
2079:
2075:
2054:
2051:
2046:
2043:
2039:
2018:
2015:
2012:
1989:
1983:
1980:
1977:
1974:
1971:
1965:
1962:
1959:
1956:
1931:
1928:
1924:
1920:
1917:
1908:
1905:
1902:
1896:
1893:
1890:
1885:
1881:
1877:
1872:
1868:
1860:
1859:
1858:
1841:
1838:
1835:
1829:
1809:
1806:
1803:
1798:
1795:
1791:
1768:
1764:
1760:
1755:
1751:
1742:
1724:
1721:
1717:
1713:
1708:
1704:
1700:
1695:
1691:
1667:
1664:
1659:
1656:
1652:
1631:
1628:
1623:
1619:
1615:
1610:
1606:
1598:
1597:
1596:
1580:
1558:
1549:
1536:
1533:
1513:
1491:
1487:
1464:
1460:
1437:
1434:
1430:
1409:
1406:
1386:
1379:implies city
1364:
1360:
1356:
1351:
1347:
1324:
1301:
1297:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1236:
1233:
1229:
1214:
1211:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1151:
1148:
1143:
1140:
1136:
1130:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1103:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1044:
1041:
1036:
1033:
1029:
1023:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
996:
988:
987:
986:
972:
969:
949:
946:
941:
938:
934:
911:
908:
905:
895:
892:
888:
861:
856:
853:
849:
843:
840:
836:
830:
825:
822:
819:
816:
813:
810:
807:
803:
797:
792:
789:
786:
782:
774:
773:
772:
741:
734:
726:
716:
710:
705:
700:
697:
693:
685:
684:
683:
669:
649:
629:
626:
621:
618:
614:
593:
590:
587:
584:
581:
572:
570:
556:
552:
549:
545:
542:
539:
534:
529:
528:semiconductor
525:
521:
517:
513:
509:
505:
501:
497:
493:
490:
486:
482:
479:
475:
471:
467:
463:
462:
456:
454:
450:
446:
442:
441:symmetric TSP
432:
430:
426:
422:
418:
414:
410:
401:
387:
384:
380:
376:
372:
368:
363:
361:
356:
354:
350:
346:
342:
338:
335:
331:
326:
324:
320:
316:
312:
308:
303:
301:
297:
293:
288:
286:
281:
280:cutting plane
277:
273:
269:
265:
261:
257:
252:
250:
246:
242:
238:
234:
228:
226:
223:We denote by
220:
218:
215:, notably by
214:
210:
206:
203:. Hamilton's
202:
198:
189:
185:
183:
179:
169:
167:
162:
158:
154:
150:
146:
142:
138:
133:
131:
127:
123:
118:
116:
115:exponentially
112:
108:
105:
101:
97:
93:
89:
84:
82:
78:
74:
69:
67:
63:
59:
55:
51:
47:
43:
34:
30:
19:
10703:
10665:
10655:
10630:
10626:
10607:
10591:
10587:
10583:
10542:(1): 34â45.
10539:
10535:
10501:
10497:
10477:
10463:
10435:
10407:
10403:
10373:
10353:
10320:
10316:
10281:
10245:
10241:
10218:
10188:
10177:the original
10138:
10134:
10105:
10062:(1): 27â36,
10059:
10055:
10045:
10041:
10028:
9999:
9993:
9962:
9958:
9930:
9926:
9899:
9885:
9859:
9855:
9845:
9828:
9824:
9790:
9786:
9776:
9722:
9690:
9686:
9676:
9635:
9631:
9594:
9588:
9551:
9545:
9519:
9494:
9490:
9478:. Retrieved
9474:
9464:
9452:. Retrieved
9448:
9439:
9413:
9400:
9359:
9355:
9349:
9339:
9334:
9315:
9311:
9273:
9269:
9262:
9217:
9213:
9203:
9162:
9158:
9152:
9135:
9131:
9124:
9089:
9085:
9075:
9048:
9044:
9034:
8983:
8979:
8973:
8938:
8934:
8928:
8901:
8897:
8891:
8879:
8867:
8855:
8843:
8798:
8785:
8750:
8740:
8728:
8719:
8715:
8701:
8689:
8677:
8662:
8644:
8635:
8626:
8612:(1): 72â89.
8609:
8603:
8590:
8573:
8569:
8563:
8551:
8532:
8528:
8518:
8501:
8495:
8489:
8455:
8451:
8441:
8424:
8418:
8412:
8405:Arora (1998)
8400:
8388:
8376:
8364:
8331:
8325:
8319:
8271:(2): 73â81.
8268:
8264:
8258:
8225:
8221:
8208:
8191:
8187:
8181:
8146:
8142:
8136:
8119:
8113:
8077:
8071:
8051:
8047:
8037:
8028:
7993:. Retrieved
7983:
7962:
7950:
7915:
7905:
7893:
7874:
7857:
7853:
7847:
7836:
7831:
7814:
7810:
7804:
7769:
7765:
7759:
7743:
7738:
7729:
7719:
7713:
7705:
7699:
7685:
7678:
7645:
7639:
7586:
7569:
7557:. Retrieved
7553:
7540:
7528:. Retrieved
7524:
7514:
7479:
7475:
7434:
7422:. Retrieved
7413:
7406:
7386:
7357:Botenproblem
7356:
7347:
7337:
7332:
7324:
7316:
7305:
7280:
7276:
7270:
7163:
7148:
7136:
7131:
7119:
7113:
7108:
7098:
7048:
7046:
6998:
6979:
6953:
6949:
6931:
6860:
5687:
5469:
5253:
5239:
5227:
5221:
5098:
5094:
5093:The weight â
5092:
5077:
5065:
5049:
5040:
5021:
5015:
5008:
4990:
4980:
4965:
4952:
4940:
4933:
4928:
4923:
4918:
4913:
4908:
4892:
4888:
4884:
4882:
4865:
4850:
4835:
4828:
4823:
4818:
4802:
4798:
4794:
4790:
4786:
4784:
4774:
4770:
4766:
4762:
4760:
4752:
4733:
4639:
4635:
4631:
4629:
4624:
4620:
4616:
4612:
4605:
4593:square roots
4574:
4564:
4560:
4523:
4516:
4510:
4506:
4491:
4487:
4474:
4463:
4392:
4388:
4384:
4374:
4365:
4361:
4359:
4324:
4321:
4308:
4304:
4297:Marco Dorigo
4291:
4273:
4237:
4233:Markov chain
4230:
4220:
4212:
4187:
4183:
4179:
4177:
4171:
4159:
4157:
4151:
4147:
4141:
4128:
4120:
4114:
4108:
4014:
4009:
4005:
4001:
3991:
3989:
3958:
3914:
3851:
3832:
3800:
3788:bitonic tour
3785:
3733:
3723:
3707:
3692:
3678:
3672:
3643:proposed by
3638:
3594:
3511:
3446:
3402:permutations
3399:
3372:
3357:
3355:
2913:
2909:
2871:
2783:and define:
2780:
2778:
2769:
2238:
2125:
2004:
1740:
1682:
1550:
1220:
1209:
1207:
876:
770:
573:
566:
468:is: Given a
466:graph theory
448:
440:
438:
406:
382:
364:
357:
347:problem was
339:
330:Christofides
327:
304:
289:
260:Santa Monica
253:
230:
224:
222:
205:icosian game
194:
175:
156:
152:
134:
119:
107:running time
95:
91:
85:
70:
49:
45:
41:
39:
29:
10669:, CMS Press
10658:, CMS Press
9927:SIAM Review
9821:Karp, R. M.
9516:Cook, W. J.
9276:: 387â399.
8791:Traub, Vera
8669:Mannila, H.
8497:Mathematika
7995:11 November
7482:: 118â127.
7256:Monge array
7246:Arc routing
7012: [
6958:NP-complete
6944:), and the
6102:Lower bound
5951:Few proved
5815:Upper bound
5690:almost-sure
4748:Gödel Prize
4623:) time for
4295:researcher
4276:convex hull
4262:), and the
4248:tabu search
4205:tabu search
390:Description
353:NP-hardness
349:NP-complete
307:mathematics
217:Karl Menger
182:Switzerland
100:NP-complete
56:problem in
10721:Categories
9933:: 60â100,
9507:References
9454:10 October
8808:1912.00670
8265:Biosystems
7779:1805.06997
7596:2007.01409
7559:13 October
7489:2004.02437
7145:Benchmarks
7009:Jens Vygen
7005:Vera Traub
5440:when
5359:, and let
4885:ghost node
4757:Asymmetric
4362:metric TSP
4231:Optimized
3695:heuristics
2849:otherwise.
748:otherwise.
606:and takes
247:report by
145:microchips
126:heuristics
104:worst-case
10612:CiteSeerX
10556:1430-2772
10426:0166-218X
10193:CiteSeerX
10151:CiteSeerX
10094:119293287
10069:1311.6338
10020:K. Aardal
9869:1303.6437
9795:CiteSeerX
9728:CiteSeerX
9693:: 61â63,
9668:122062088
9660:0305-0041
9556:CiteSeerX
9423:1303.4969
9416:: 2, 13,
9376:1435-9456
9179:0340-0727
9108:0090-502X
9067:1932-6246
9010:0090-502X
8988:CiteSeerX
8965:1932-6246
8943:CiteSeerX
8835:208527125
8465:1307.0221
8281:CiteSeerX
8242:2334-0843
8151:CiteSeerX
8082:CiteSeerX
7623:220347561
7506:214803097
7297:0028-3045
7101:Euclidean
7068:ε
7032:ε
6893:≳
6888:∗
6825:≳
6820:∗
6767:∗
6754:≃
6748:β
6726:∗
6639:≥
6631:∗
6508:≥
6500:∗
6446:≠
6343:∗
6277:≥
6269:∗
6215:≠
6133:∗
6085:…
6079:≤
6076:β
6043:≤
6040:β
6013:≤
6010:β
5974:≤
5969:∗
5877:≤
5874:β
5838:≤
5833:∗
5786:…
5753:∞
5750:→
5727:β
5724:→
5712:∗
5668:∗
5630:β
5593:∗
5570:∞
5567:→
5553:β
5513:≤
5508:∗
5478:β
5450:∞
5447:→
5435:β
5432:→
5420:∗
5377:∗
5275:…
5198:→
5192:→
5186:→
5158:→
5147:→
5141:→
5130:→
5124:→
5113:→
4706:−
4671:
4571:Euclidean
4419:≤
4366:delta-TSP
4164:Bell Labs
4074:
3807:matchings
3754:
3745:Θ
3442:factorial
3377:Devising
3334:≥
3306:…
3294:⊊
3288:∀
3279:−
3263:≤
3239:∈
3227:≠
3220:∑
3210:∈
3203:∑
3183:…
3136:≠
3117:∑
3097:…
3050:≠
3031:∑
3018::
2967:≠
2960:∑
2939:∑
2745:≤
2739:≤
2723:≤
2710:≤
2694:≤
2688:≠
2682:≤
2657:−
2642:−
2627:≤
2608:−
2582:…
2531:≠
2512:∑
2495:…
2444:≠
2425:∑
2408:…
2363:∈
2341::
2286:≠
2279:∑
2258:∑
2016:−
1978:…
1966:∈
1921:−
1906:−
1897:≤
1878:−
1839:−
1761:≥
1701:≥
1616:≥
1559:≥
1271:…
1184:…
1123:≠
1104:∑
1077:…
1016:≠
997:∑
811:≠
804:∑
783:∑
588:…
515:problem).
367:Applegate
328:In 1976,
315:chemistry
290:In 1959,
141:logistics
122:benchmark
10647:14764079
10564:11505612
10528:38355042
10461:(eds.),
10345:44960960
10311:(1954),
10216:(2012).
10126:(1994),
10002:: 1â11,
9947:18516138
9817:Held, M.
9768:TR05-069
9709:15649582
9580:(1998),
9518:(2006),
9480:26 April
9475:Wired UK
9445:"TSPLIB"
9392:14994429
9384:21965161
9290:53761995
9254:29264418
9187:28608230
9116:15190718
9026:18989303
9018:12749463
8777:12391033
8652:Archived
8250:18691261
8228:: 2â10.
8027:(eds.).
7942:49743824
7585:(eds.),
7277:Networks
7184:See also
7170:P vs. NP
7134:amoeboid
6940:FP; see
6002:, hence
5820:One has
5254:Suppose
5154:′
5137:′
5120:′
5066:C′
5041:B′
5016:A′
4934:C′
4929:B′
4924:A′
4738:(PTAS).
4313:emergent
4192:Shen Lin
4135:problem.
3918:matching
3801:Another
3693:Various
3599:Various
2912:to city
1526:to city
662:to city
413:vertices
383:Concorde
157:distance
137:planning
79:and the
10697:at the
10684:at the
10572:8986203
10520:8934685
10378:Bibcode
10207:4622707
10173:7973651
10143:Bibcode
10135:Science
10074:Bibcode
10048:: 80â86
9981:0455550
9918:6331426
9760:9054176
9640:Bibcode
9619:3023351
9611:1668147
9428:Bibcode
9245:5727545
9222:Bibcode
9214:Heliyon
9195:3959429
8920:8934685
8722:: 76â79
8632:"error"
8482:8904077
8356:0188872
8348:2313333
8311:8243011
8303:9231906
8273:Bibcode
8173:8130854
7973:YouTube
7796:6941484
7670:2856898
7662:2774420
7530:14 June
7049:longest
6934:NP-hard
4501:In the
4360:In the
4303:called
4098:
4054:
4050:
4021:
3916:weight
3892:
3863:
3451:is the
439:In the
375:ChvĂĄtal
319:physics
213:Harvard
178:Germany
172:History
86:In the
54:NP-hard
10645:
10614:
10570:
10562:
10554:
10526:
10518:
10485:
10443:
10424:
10388:
10361:
10343:
10337:166695
10335:
10289:
10226:
10205:
10195:
10171:
10153:
10092:
9979:
9945:
9916:
9906:
9797:
9766:
9758:
9748:
9730:
9707:
9666:
9658:
9617:
9609:
9558:
9526:
9390:
9382:
9374:
9288:
9252:
9242:
9193:
9185:
9177:
9114:
9106:
9065:
9024:
9016:
9008:
8990:
8963:
8945:
8918:
8833:
8823:
8775:
8765:
8480:
8354:
8346:
8309:
8301:
8283:
8248:
8240:
8171:
8153:
8102:
8084:
7940:
7930:
7837:J. ACM
7794:
7750:
7668:
7660:
7621:
7611:
7504:
7394:
7295:
6986:metric
6960:. The
6956:") is
6896:0.7078
6828:0.7080
5692:limit
5470:where
4509:- and
4490:- and
4466:metric
4377:metric
4356:Metric
3651:, and
3531:1.9999
3440:, the
1739:would
548:Google
425:vertex
421:vertex
377:, and
270:, and
75:, the
10643:S2CID
10568:S2CID
10524:S2CID
10468:(PDF)
10341:S2CID
10333:JSTOR
10203:JSTOR
10180:(PDF)
10131:(PDF)
10090:S2CID
10064:arXiv
10033:(PDF)
9943:S2CID
9864:arXiv
9756:S2CID
9705:S2CID
9664:S2CID
9615:S2CID
9585:(PDF)
9542:(PDF)
9418:arXiv
9410:(PDF)
9388:S2CID
9318:(2),
9286:S2CID
9191:S2CID
9051:(2).
9022:S2CID
8941:(1).
8831:S2CID
8803:arXiv
8773:S2CID
8712:(PDF)
8478:S2CID
8460:arXiv
8344:JSTOR
8307:S2CID
8246:S2CID
8218:(PDF)
8169:S2CID
8021:(PDF)
7938:S2CID
7792:S2CID
7774:arXiv
7691:(PDF)
7666:S2CID
7619:S2CID
7591:arXiv
7525:WIRED
7502:S2CID
7484:arXiv
7424:2 May
7418:(PDF)
7262:Notes
7016:]
6909:0.551
6841:0.522
6046:0.984
5545:that
4258:(see
3998:3-opt
3993:2-opt
3571:1.728
2872:Take
1783:when
512:drill
417:edges
371:Bixby
10560:PMID
10552:ISSN
10516:PMID
10483:ISBN
10441:ISBN
10422:ISSN
10386:ISBN
10359:ISBN
10287:ISBN
10224:ISBN
10169:PMID
9914:OCLC
9904:ISBN
9764:ECCC
9746:ISBN
9656:ISSN
9524:ISBN
9482:2012
9456:2020
9380:PMID
9372:ISSN
9342:1(1)
9250:PMID
9183:PMID
9175:ISSN
9112:PMID
9104:ISSN
9063:ISSN
9014:PMID
9006:ISSN
8961:ISSN
8916:PMID
8821:ISBN
8763:ISBN
8299:PMID
8238:ISSN
8100:ISBN
8066:>
7997:2020
7928:ISBN
7748:ISBN
7609:ISBN
7561:2020
7532:2015
7426:2020
7392:ISBN
7293:ISSN
7007:and
6670:5184
6082:0.73
5990:1.75
5688:The
5300:are
4793:and
4742:and
4619:log
4563:and
4207:and
4194:and
4115:The
3833:The
3786:The
3724:The
3697:and
3663:and
2893:>
2094:and
1581:>
1357:<
1164:for
1095:and
1057:for
627:>
553:The
518:The
504:edge
379:Cook
180:and
153:city
128:and
71:The
64:and
40:The
10635:doi
10596:doi
10544:doi
10506:doi
10412:doi
10408:117
10325:doi
10250:doi
10161:doi
10139:266
10082:doi
10004:doi
9967:doi
9935:doi
9874:doi
9833:doi
9805:doi
9738:doi
9695:doi
9648:doi
9599:doi
9566:doi
9364:doi
9320:doi
9278:doi
9240:PMC
9230:doi
9167:doi
9140:doi
9094:doi
9053:doi
8998:doi
8953:doi
8906:doi
8813:doi
8755:doi
8614:doi
8578:doi
8537:doi
8506:doi
8470:doi
8429:doi
8336:doi
8291:doi
8230:doi
8196:doi
8161:doi
8124:doi
8092:doi
8056:doi
8052:117
7971:on
7920:doi
7862:doi
7819:doi
7815:236
7784:doi
7650:doi
7646:211
7601:doi
7494:doi
7285:doi
6990:APX
6982:NPO
5739:as
5560:lim
5230:of
5214:).
4773:to
4765:to
4668:log
4387:to
4305:ACS
4071:log
3861:in
3751:log
3728:(a
2931:min
2254:min
1741:not
1644:if
1210:one
258:in
239:at
50:TSP
10723::
10641:.
10629:.
10592:28
10590:,
10566:.
10558:.
10550:.
10540:65
10538:.
10522:,
10514:,
10502:58
10500:,
10420:.
10406:.
10402:.
10384:,
10339:,
10331:,
10319:,
10315:,
10307:;
10303:;
10279:.
10271:;
10267:;
10263:;
10246:19
10244:,
10201:,
10167:,
10159:,
10149:,
10137:,
10133:,
10088:,
10080:,
10072:,
10060:47
10058:,
10046:25
10044:,
10022:;
10000:18
9998:,
9977:MR
9975:,
9961:,
9941:,
9931:33
9929:,
9912:,
9898:,
9872:,
9860:81
9858:,
9829:10
9827:,
9819:;
9803:,
9791:75
9789:,
9762:,
9754:,
9744:,
9736:,
9703:,
9689:,
9662:,
9654:,
9646:,
9636:55
9634:,
9630:,
9613:,
9607:MR
9605:,
9595:45
9593:,
9587:,
9564:,
9552:38
9550:,
9544:,
9473:.
9447:.
9426:,
9412:,
9386:.
9378:.
9370:.
9360:15
9358:.
9314:,
9310:,
9298:^
9284:.
9274:52
9272:.
9248:.
9238:.
9228:.
9216:.
9212:.
9189:.
9181:.
9173:.
9163:82
9161:.
9136:36
9134:.
9110:.
9102:.
9090:32
9088:.
9084:.
9061:.
9047:.
9043:.
9020:.
9012:.
9004:.
8996:.
8984:31
8982:.
8959:.
8951:.
8937:.
8914:,
8902:58
8900:,
8829:.
8819:.
8811:.
8797:.
8771:.
8761:.
8749:.
8720:17
8714:,
8634:.
8610:16
8608:.
8598:;
8574:18
8572:.
8533:51
8531:.
8527:.
8500:.
8476:,
8468:,
8456:26
8454:,
8423:.
8352:MR
8350:.
8342:.
8332:72
8330:.
8305:.
8297:.
8289:.
8279:.
8269:43
8267:.
8244:.
8236:.
8226:23
8224:.
8220:.
8192:32
8190:.
8167:.
8159:.
8147:26
8145:.
8098:,
8090:,
8050:.
8046:.
8005:^
7936:.
7926:.
7914:.
7885:,
7881:,
7856:.
7813:.
7790:.
7782:.
7770:45
7768:.
7664:,
7658:MR
7656:,
7644:,
7630:^
7617:,
7607:,
7599:,
7581:;
7552:.
7523:.
7500:.
7492:.
7480:53
7478:.
7464:^
7447:^
7364:^
7291:.
7281:43
7279:.
7154:.
7079:25
7062:33
7026:22
7014:de
6667:19
5685:.
5246:.
4985:4
4960:5
4860:3
4845:2
4805:.
4789:,
4395::
4372:.
4266:.
4254:,
4250:,
4246:,
4242:,
3956:.
3798:.
3685:.
3647:,
3592:.
3365:.
3337:2.
2181:1.
1668:1.
1593:),
373:,
369:,
362:.
317:,
313:,
309:,
266:,
139:,
68:.
10649:.
10637::
10631:6
10620:.
10598::
10584:k
10574:.
10546::
10508::
10491:.
10449:.
10428:.
10414::
10380::
10367:.
10327::
10321:2
10295:.
10252::
10232:.
10163::
10145::
10110:.
10097:.
10084::
10076::
10066::
10050:.
10011:.
10006::
9984:.
9969::
9963:4
9950:.
9937::
9921:.
9890:.
9876::
9866::
9850:.
9840:.
9835::
9812:.
9807::
9781:.
9771:.
9740::
9712:.
9697::
9691:9
9681:.
9671:.
9650::
9642::
9622:.
9601::
9573:.
9568::
9533:.
9484:.
9458:.
9430::
9420::
9394:.
9366::
9329:.
9322::
9316:3
9292:.
9280::
9256:.
9232::
9224::
9218:3
9197:.
9169::
9146:.
9142::
9118:.
9096::
9069:.
9055::
9049:3
9028:.
9000::
8967:.
8955::
8939:1
8923:.
8908::
8886:.
8874:.
8862:.
8850:.
8837:.
8815::
8805::
8779:.
8757::
8735:.
8696:.
8684:.
8638:.
8620:.
8616::
8584:.
8580::
8558:.
8545:.
8539::
8512:.
8508::
8502:2
8472::
8462::
8435:.
8431::
8425:2
8407:.
8395:.
8383:.
8371:.
8358:.
8338::
8313:.
8293::
8275::
8252:.
8232::
8202:.
8198::
8175:.
8163::
8130:.
8126::
8094::
8064:.
8058::
7999:.
7957:.
7944:.
7922::
7900:.
7868:.
7864::
7858:2
7825:.
7821::
7798:.
7786::
7776::
7693:.
7684:"
7673:.
7652::
7603::
7593::
7563:.
7534:.
7508:.
7496::
7486::
7459:.
7442:.
7400:.
7327:)
7299:.
7287::
7172:.
7075:/
7071:)
7065:+
7059:(
7029:+
6954:x
6950:x
6921:.
6906:+
6901:n
6883:n
6879:L
6844:,
6838:+
6833:n
6815:n
6811:L
6784:)
6779:n
6773:/
6762:n
6758:L
6751:(
6721:n
6717:L
6690:,
6685:n
6678:)
6661:+
6655:8
6652:5
6644:(
6636:]
6626:n
6622:L
6618:[
6614:E
6581:,
6576:n
6568:8
6565:5
6559:=
6554:n
6547:)
6539:8
6536:3
6530:+
6524:4
6521:1
6513:(
6505:]
6495:n
6491:L
6487:[
6483:E
6454:0
6450:X
6441:j
6437:X
6433:,
6428:i
6424:X
6401:0
6397:X
6376:2
6372:/
6368:n
6348:]
6338:n
6334:L
6330:[
6326:E
6299:.
6294:n
6286:2
6283:1
6274:]
6264:n
6260:L
6256:[
6252:E
6223:0
6219:X
6210:i
6206:X
6183:0
6179:X
6158:n
6138:]
6128:n
6124:L
6120:[
6116:E
6097:.
6065:.
6051:2
6018:2
5987:+
5982:n
5979:2
5964:n
5960:L
5934:n
5928:/
5924:1
5902:n
5880:2
5854:2
5851:+
5846:n
5841:2
5829:L
5797:n
5793:X
5789:,
5783:,
5778:1
5774:X
5747:n
5718:n
5707:n
5703:L
5673:]
5663:n
5659:L
5655:[
5651:E
5608:n
5602:/
5598:]
5588:n
5584:L
5580:[
5576:E
5564:n
5556:=
5529:2
5526:+
5521:n
5516:2
5503:n
5499:L
5453:,
5444:n
5426:n
5415:n
5411:L
5372:n
5368:L
5345:2
5341:]
5337:1
5334:,
5331:0
5328:[
5308:n
5286:n
5282:X
5278:,
5272:,
5267:1
5263:X
5240:E
5228:E
5201:A
5195:B
5189:C
5183:A
5161:A
5151:B
5144:B
5134:C
5127:C
5117:A
5110:A
5099:w
5095:w
5078:w
5076:â
5073:4
5070:5
5054:3
5050:w
5048:â
5045:6
5029:2
5026:1
5022:w
5020:â
5009:w
5007:â
5004:3
5001:2
4991:C
4981:w
4979:â
4976:1
4966:B
4957:6
4953:w
4951:â
4941:A
4919:C
4914:B
4909:A
4893:w
4889:w
4873:4
4870:5
4866:C
4855:6
4851:B
4842:1
4836:A
4829:C
4824:B
4819:A
4803:N
4799:N
4795:C
4791:B
4787:A
4775:A
4771:B
4767:B
4763:A
4717:)
4709:1
4703:d
4699:)
4693:d
4688:c
4685:(
4682:O
4678:)
4674:n
4665:(
4662:n
4658:(
4653:O
4640:c
4636:d
4632:c
4625:n
4621:n
4617:n
4615:(
4613:O
4565:B
4561:A
4541:B
4538:A
4534:d
4511:y
4507:x
4492:y
4488:x
4460:.
4446:B
4443:C
4439:d
4435:+
4430:C
4427:A
4423:d
4414:B
4411:A
4407:d
4393:C
4389:B
4385:A
4338:.
4307:(
4221:V
4213:V
4188:k
4184:k
4180:k
4172:V
4160:k
4152:k
4148:k
4142:k
4140:2
4129:k
4121:V
4109:k
4086:)
4083:)
4080:n
4077:(
4068:n
4065:(
4062:O
4038:)
4035:n
4032:(
4029:O
4010:k
4002:k
3944:)
3939:3
3935:n
3931:(
3928:O
3880:)
3877:n
3874:(
3871:O
3770:)
3766:|
3762:V
3758:|
3748:(
3734:N
3635:.
3580:)
3575:n
3567:(
3564:O
3540:)
3535:n
3527:(
3524:O
3489:)
3484:n
3480:2
3474:2
3470:n
3466:(
3463:O
3428:)
3425:!
3422:n
3419:(
3416:O
3330:|
3326:Q
3322:|
3318:,
3315:}
3312:n
3309:,
3303:,
3300:1
3297:{
3291:Q
3282:1
3275:|
3271:Q
3267:|
3256:j
3253:i
3249:x
3242:Q
3236:j
3233:,
3230:i
3224:j
3213:Q
3207:i
3192:;
3189:n
3186:,
3180:,
3177:1
3174:=
3171:i
3165:1
3162:=
3157:j
3154:i
3150:x
3144:n
3139:i
3133:j
3130:,
3127:1
3124:=
3121:j
3106:;
3103:n
3100:,
3094:,
3091:1
3088:=
3085:j
3079:1
3076:=
3071:j
3068:i
3064:x
3058:n
3053:j
3047:i
3044:,
3041:1
3038:=
3035:i
3013:j
3010:i
3006:x
3000:j
2997:i
2993:c
2987:n
2982:1
2979:=
2976:j
2973:,
2970:i
2964:j
2954:n
2949:1
2946:=
2943:i
2914:j
2910:i
2896:0
2888:j
2885:i
2881:c
2843:0
2836:j
2828:i
2818:1
2812:{
2807:=
2802:j
2799:i
2795:x
2781:n
2751:.
2748:n
2742:i
2736:2
2730:n
2718:i
2714:u
2707:2
2700:;
2697:n
2691:j
2685:i
2679:2
2673:)
2668:j
2665:i
2661:x
2654:1
2651:(
2648:)
2645:1
2639:n
2636:(
2624:1
2621:+
2616:j
2612:u
2603:i
2599:u
2591:;
2588:n
2585:,
2579:,
2576:1
2573:=
2570:i
2564:1
2557:=
2552:j
2549:i
2545:x
2539:n
2534:i
2528:j
2525:,
2522:1
2519:=
2516:j
2504:;
2501:n
2498:,
2492:,
2489:1
2486:=
2483:j
2477:1
2470:=
2465:j
2462:i
2458:x
2452:n
2447:j
2441:i
2438:,
2435:1
2432:=
2429:i
2417:;
2414:n
2411:,
2405:,
2402:1
2399:=
2396:j
2393:,
2390:i
2384:}
2381:1
2378:,
2375:0
2372:{
2358:j
2355:i
2351:x
2332:j
2329:i
2325:x
2319:j
2316:i
2312:c
2306:n
2301:1
2298:=
2295:j
2292:,
2289:i
2283:j
2273:n
2268:1
2265:=
2262:i
2224:1
2204:,
2201:1
2161:1
2139:i
2135:u
2112:.
2107:i
2103:u
2080:j
2076:u
2055:0
2052:=
2047:j
2044:i
2040:x
2019:1
2013:n
1990:,
1987:}
1984:n
1981:,
1975:,
1972:2
1969:{
1963:j
1960:,
1957:i
1937:)
1932:j
1929:i
1925:x
1918:1
1915:(
1912:)
1909:1
1903:n
1900:(
1894:1
1891:+
1886:j
1882:u
1873:i
1869:u
1845:)
1842:1
1836:n
1833:(
1830:n
1810:,
1807:0
1804:=
1799:j
1796:i
1792:x
1769:i
1765:u
1756:j
1752:u
1725:j
1722:i
1718:x
1714:+
1709:i
1705:u
1696:j
1692:u
1665:=
1660:j
1657:i
1653:x
1632:1
1629:+
1624:i
1620:u
1611:j
1607:u
1573:(
1537:.
1534:i
1514:1
1492:i
1488:u
1465:i
1461:u
1438:j
1435:i
1431:x
1410:.
1407:j
1387:i
1365:j
1361:u
1352:i
1348:u
1337:;
1325:1
1302:i
1298:u
1277:n
1274:,
1268:,
1265:1
1262:=
1259:i
1237:j
1234:i
1230:x
1193:.
1190:n
1187:,
1181:,
1178:1
1175:=
1172:i
1152:1
1149:=
1144:j
1141:i
1137:x
1131:n
1126:i
1120:j
1117:,
1114:1
1111:=
1108:j
1083:n
1080:,
1074:,
1071:1
1068:=
1065:j
1045:1
1042:=
1037:j
1034:i
1030:x
1024:n
1019:j
1013:i
1010:,
1007:1
1004:=
1001:i
973:n
970:2
950:0
947:=
942:j
939:i
935:x
912:j
909:,
906:i
902:}
896:j
893:i
889:x
885:{
862:.
857:j
854:i
850:x
844:j
841:i
837:c
831:n
826:1
823:=
820:j
817:,
814:i
808:j
798:n
793:1
790:=
787:i
742:0
735:j
727:i
717:1
711:{
706:=
701:j
698:i
694:x
670:j
650:i
630:0
622:j
619:i
615:c
594:n
591:,
585:,
582:1
540:.
491:.
96:L
92:L
48:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
