Misplaced Pages

#382617

66-464: A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean traveling salesman problem , a PTAS would produce a tour with length at most (1 + ε) L , with L being the length of the shortest tour. The running time of

132-548: 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. Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete , which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours. Great progress

198-402: A PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time O ( n ) or even O ( n ) counts as a PTAS. A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O ( n ) . One way of addressing this is to define

264-514: A big advance in this direction: the Christofides-Serdyukov algorithm 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 remained the method with the best worst-case scenario until 2011, when

330-426: A departure to exactly one other city. The last constraint enforces that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities. Label the cities with the numbers 1, ..., n and define: Take c i j > 0 {\displaystyle c_{ij}>0} to be the distance from city i to city j . Then TSP can be written as

396-421: A different level. All NP-complete problems are also NP-hard (see List of NP-complete problems ). For example, the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph—commonly known as the travelling salesman problem —is NP-hard. The subset sum problem is another example: given a set of integers, does any non-empty subset of them add up to zero? That

462-473: A dummy variable u i {\displaystyle u_{i}} that keeps track of the order in which the cities are visited, counting from city 1 {\displaystyle 1} ; the interpretation is that u i < u j {\displaystyle u_{i}<u_{j}} implies city i {\displaystyle i} is visited before city j . {\displaystyle j.} For

528-711: A given tour (as encoded into values of the x i j {\displaystyle x_{ij}} variables), one may find satisfying values for the u i {\displaystyle u_{i}} variables by making u i {\displaystyle u_{i}} equal to the number of edges along that tour, when going from city 1 {\displaystyle 1} to city i . {\displaystyle i.} Because linear programming favors non-strict inequalities ( ≥ {\displaystyle \geq } ) over strict ( > {\displaystyle >} ), we would like to impose constraints to

594-612: 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 obtained by the NN algorithm for further improvement in an elitist model, where only better solutions are accepted. The bitonic tour of a set of points is the minimum-perimeter monotone polygon that has the points as its vertices; it can be computed efficiently with dynamic programming . Another constructive heuristic , Match Twice and Stitch (MTS), performs two sequential matchings , where

660-425: 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 even order, which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov: The pairwise exchange or 2-opt technique involves iteratively removing two edges and replacing them with two different edges that reconnect

726-509: A method for finding an Eulerian tour to find a TSP solution. By the triangle inequality , 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. 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

SECTION 10

#1732801545383

792-436: 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. TSP can be modeled as an undirected weighted graph , such that cities are the graph's vertices , paths are the graph's edges , and a path's distance is the edge's weight. It is a minimization problem starting and finishing at

858-569: A polynomial factor of O ( n ! ) {\displaystyle O(n!)} , the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is the Held–;Karp algorithm , which solves the problem in time O ( n 2 2 n ) {\displaystyle O(n^{2}2^{n})} . This bound has also been reached by Exclusion-Inclusion in an attempt preceding

924-407: 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 Eulerian graph , we can find an Eulerian tour in ⁠ O ( n ) {\displaystyle O(n)} ⁠ 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

990-399: A salesman who starts at a home or office and visits a fixed number of locations before returning to the start. In the following decades, the problem was studied by many researchers from mathematics , computer science , chemistry , physics , and other sciences. In the 1960s, however, a new approach was created that, instead of seeking optimal solutions, would produce a solution whose length

1056-573: A school bus routing problem. Hassler Whitney at Princeton University generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling [or traveling] salesman problem" was the 1949 RAND Corporation report by Julia Robinson , "On the Hamiltonian game (a traveling salesman problem)." In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and

1122-454: A specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (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. In the symmetric TSP , the distance between two cities is the same in each opposite direction, forming an undirected graph . This symmetry halves

1188-473: 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 branch-and-bound algorithms perhaps for

1254-415: A sub-problem in many areas, such as DNA sequencing . In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between

1320-414: 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. In addition to the x i j {\displaystyle x_{ij}} variables as above, there is for each i = 1 , … , n {\displaystyle i=1,\ldots ,n}

1386-472: A subtour of the cities of Q. Because this leads to an exponential number of possible constraints, in practice it is solved with row generation . The traditional lines of attack for the NP-hard problems are the following: The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute-force search ). The running time for this approach lies within

SECTION 20

#1732801545383

1452-456: Is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H . Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H . As any problem L in NP reduces in polynomial time to G , L reduces in turn to H in polynomial time so this new definition implies the previous one. It does not restrict

1518-500: Is a decision problem and happens to be NP-complete. There are decision problems that are NP-hard but not NP-complete such as the halting problem . That is the problem which asks "given a program and its input, will it run forever?" That is a yes / no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to

1584-435: Is an algorithm which takes an instance of an optimization or counting problem and a parameter ε > 0 and, in polynomial time, produces a solution that has a high probability of being within a factor ε of optimal. Conventionally, "high probability" means probability greater than 3/4, though as with most probabilistic complexity classes the definition is robust to variations in this exact value (the bare minimum requirement

1650-426: Is at most L ) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially ) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though

1716-420: Is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time , there is a polynomial-time reduction from L to H . That is, assuming a solution for H takes 1 unit time, H ' s solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all

1782-412: Is exactly one incoming edge and one outgoing edge, which may be expressed as the 2 n {\displaystyle 2n} linear equations 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 one tour which visits all vertices, as the edges chosen could make up several tours, each visiting only

1848-531: Is generally greater than 1/2). Like a PTAS, a PRAS must have running time polynomial in n , but not necessarily in ε ; with further restrictions on the running time in ε , one can define an efficient polynomial-time randomized approximation scheme or EPRAS similar to the EPTAS, and a fully polynomial-time randomized approximation scheme or FPRAS similar to the FPTAS. The term PTAS may also be used to refer to

1914-528: Is not correct. Instead MTZ use the n ( n − 1 ) {\displaystyle n(n-1)} linear constraints where the constant term n − 1 {\displaystyle n-1} provides sufficient slack that x i j = 0 {\displaystyle x_{ij}=0} does not impose a relation between u j {\displaystyle u_{j}} and u i . {\displaystyle u_{i}.} The way that

1980-488: 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 minimum spanning tree 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. In 1976, Christofides and Serdyukov (independently of each other) made

2046-417: 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. It was first considered mathematically in the 1930s by Merrill M. Flood who was looking to solve

Polynomial-time approximation scheme - Misplaced Pages Continue

2112-487: Is the quasi-polynomial-time approximation scheme or QPTAS . A QPTAS has time complexity n for each fixed ε > 0 . Furthermore, a PTAS can run in FPT time for some parameterization of the problem, which leads to a parameterized approximation scheme . Some problems which do not have a PTAS may admit a randomized algorithm with similar properties, a polynomial-time randomized approximation scheme or PRAS . A PRAS

2178-492: The u i {\displaystyle u_{i}} variables then enforce that a single tour visits all cities is that they increase by at least 1 {\displaystyle 1} for each step along a tour, with a decrease only allowed where the tour passes through city  1. {\displaystyle 1.} That constraint would be violated by every tour which does not pass through city  1 , {\displaystyle 1,} so

2244-436: The { x i j } i , j {\displaystyle \{x_{ij}\}_{i,j}} 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 x i j = 0 {\displaystyle x_{ij}=0} . Therefore, both formulations also have the constraints that, at each vertex, there

2310-405: The efficient polynomial-time approximation scheme or EPTAS , in which the running time is required to be O ( n ) for a constant c independent of ε . This ensures that an increase in problem size has the same relative effect on runtime regardless of what ε is being used; however, the constant under the big-O can still depend on ε arbitrarily. In other words, an EPTAS runs in FPT time where

2376-644: 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. Common to both these formulations is that one labels the cities with the numbers 1 , … , n {\displaystyle 1,\ldots ,n} and takes c i j > 0 {\displaystyle c_{ij}>0} to be

2442-431: The NN algorithm give the worst route. This is true for both asymmetric and symmetric TSPs. Rosenkrantz et al. showed that the NN algorithm has the approximation factor Θ ( log ⁡ | V | ) {\displaystyle \Theta (\log |V|)} for instances satisfying the triangle inequality. A variation of the NN algorithm, called nearest fragment (NF) operator, which connects

2508-666: The United States after the RAND Corporation in Santa Monica offered prizes for steps in solving the problem. Notable contributions were made by George Dantzig , Delbert Ray Fulkerson , and Selmer M. Johnson from the RAND Corporation, who expressed the problem as an integer linear program and developed the cutting plane method for its solution. They wrote what is considered the seminal paper on

2574-412: 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 weight matching using algorithms with a complexity of O ( n 3 ) {\displaystyle O(n^{3})} . 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

2640-575: The class NP-hard to decision problems, and it also includes search problems or optimization problems . If P ≠ NP, then NP-hard problems could not be solved in polynomial time. Some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX ) or even up to any approximation ratio (those in PTAS or FPTAS ). There are many classes of approximability, each one enabling approximation up to

2706-486: The class of optimization problems that have a PTAS. PTAS is a subset of APX , and unless P = NP , it is a strict subset. Membership in PTAS can be shown using a PTAS reduction , L-reduction , or P-reduction , all of which preserve PTAS membership, and these may also be used to demonstrate PTAS-completeness. On the other hand, showing non-membership in PTAS (namely, the nonexistence of a PTAS), may be done by showing that

Polynomial-time approximation scheme - Misplaced Pages Continue

2772-408: The cost (distance) from city i {\displaystyle i} to city j {\displaystyle j} . The main variables in the formulations are: 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 Without further constraints,

2838-554: The dynamic programming approach. Improving these time bounds seems to be difficult. For example, it has not been determined whether a classical exact algorithm for TSP that runs in time O ( 1.9999 n ) {\displaystyle O(1.9999^{n})} exists. The currently best quantum exact algorithm for TSP due to Ambainis et al. runs in time O ( 1.728 n ) {\displaystyle O(1.728^{n})} . Other approaches include: An exact solution for 15,112 German towns from TSPLIB

2904-428: The effect that Merely requiring u j ≥ u i + x i j {\displaystyle u_{j}\geq u_{i}+x_{ij}} would not achieve that, because this also requires u j ≥ u i {\displaystyle u_{j}\geq u_{i}} when x i j = 0 , {\displaystyle x_{ij}=0,} which

2970-495: The first time. In 1959, Jillian Beardwood , J.H. Halton, and John Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of the Cambridge Philosophical Society . 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

3036-560: The following integer linear programming problem: The last constraint of the DFJ formulation—called a subtour elimination 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. Intuitively, for each proper subset Q of the cities, the constraint requires that there be fewer edges than cities in Q: if there were to be as many edges in Q as cities in Q, that would represent

3102-417: The fragments created by edge removal into a new and shorter tour. Similarly, the 3-opt technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of the k -opt method. The label Lin–Kernighan is an often heard misnomer for 2-opt; Lin–Kernighan is actually the more general k -opt method. NP-hardness In computational complexity theory , a computational problem H

3168-557: The halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable . There are also NP-hard problems that are neither NP-complete nor Undecidable . For instance,

3234-470: The number of possible solutions. In the asymmetric TSP , paths may not exist in both directions or the distances might be different, forming a directed graph . 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. The TSP can be formulated as an integer linear program . Several formulations are known. Two notable formulations are

3300-400: The only way to satisfy it is that the tour passing city  1 {\displaystyle 1} also passes through all other cities. The MTZ formulation of TSP is thus the following integer linear programming problem: 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

3366-472: The optimal solution. Several categories of heuristics are recognized. The nearest neighbour (NN) algorithm (a greedy algorithm ) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For N 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

SECTION 50

#1732801545383

3432-503: The optimal. It was one of the first approximation algorithms , and was in part responsible for drawing attention to approximation algorithms as a practical approach to intractable problems . 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. This algorithm looks at things differently by using

3498-404: The origin city?" It is an NP-hard problem in combinatorial optimization , important in theoretical computer science and operations research . The travelling purchaser problem , the vehicle routing problem and the ring star problem are three generalizations of TSP. The decision version of the TSP (where given a length L , the task is to decide whether the graph has a tour whose length

3564-399: The parameter is ε. Even more restrictive, and useful in practice, is the fully polynomial-time approximation scheme or FPTAS , which requires the algorithm to be polynomial in both the problem size n and 1/ε . Unless P = NP , it holds that FPTAS ⊊ PTAS ⊊ APX . Consequently, under this assumption, APX-hard problems do not have PTASs. Another deterministic variant of the PTAS

3630-464: The problem is APX-hard, after which the existence of a PTAS would show P = NP. APX-hardness is commonly shown via PTAS reduction or AP-reduction . Traveling salesman problem In the theory of computational complexity , the travelling salesman problem ( TSP ) 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

3696-439: The problem is computationally difficult, many heuristics and exact algorithms 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%. The TSP has several applications even in its purest formulation, such as planning , logistics , and the manufacture of microchips . Slightly modified, it appears as

3762-404: The problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic: We denote by messenger problem (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

3828-562: The problems in the complexity class NP . As it is suspected, but unproven, that P≠NP , it is unlikely that any polynomial-time algorithms for NP-hard problems exist. A simple example of an NP-hard problem is the subset sum problem . Informally, if H is NP-hard, then it is at least as difficult to solve as the problems in NP . However, the opposite direction is not true: some problems are undecidable , and therefore even more difficult to solve than all problems in NP, but they are probably not NP-hard (unless P=NP). A decision problem H

3894-399: 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. The algorithm of Christofides and Serdyukov follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight perfect matching . This gives a TSP tour which is at most 1.5 times

3960-437: The sources; in such problems, the TSP can be embedded inside an optimal control problem . In many applications, additional constraints such as limited resources or time windows may be imposed. The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland , but contains no mathematical treatment. The TSP

4026-435: 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 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

SECTION 60

#1732801545383

4092-589: 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 Concorde TSP Solver : 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

4158-399: Was found in 2001 using the cutting-plane method proposed by George Dantzig , Ray Fulkerson , and Selmer M. Johnson in 1954, based on linear programming . The computations were performed on a network of 110 processors located at Rice University and Princeton University . The total computation time was equivalent to 22.6 years on a single 500 MHz Alpha processor . In May 2004,

4224-646: 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 branch-and-bound . In the 1990s, Applegate , Bixby , Chvátal , and Cook developed the program Concorde 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 instance given by

4290-569: Was mathematically formulated in the 19th century by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman . Hamilton's icosian game was a recreational puzzle based on finding a Hamiltonian cycle . The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard , notably by Karl Menger , who defines

4356-418: Was solved using Concorde TSP Solver , taking over 136 CPU-years; see Applegate et al. (2006) . Various heuristics and approximation algorithms , which quickly yield good solutions, have been devised. These include the multi-fragment algorithm . 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

#382617