Minimum TSP: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
V: number of cities (nodes) | $V$: number of cities (nodes) | ||
E: number of roads (edges) | $E$: number of roads (edges) | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 34: | Line 34: | ||
| [[Lawler; E. L. (Minimum TSP The Traveling-Salesman Problem)|Lawler; E. L.]] || 1985 || $O({1.674}^V E^{2})$ || || Exact || Deterministic || [https://onlinelibrary.wiley.com/doi/10.1002/net.3230180309 Time] | | [[Lawler; E. L. (Minimum TSP The Traveling-Salesman Problem)|Lawler; E. L.]] || 1985 || $O({1.674}^V E^{2})$ || || Exact || Deterministic || [https://onlinelibrary.wiley.com/doi/10.1002/net.3230180309 Time] | ||
|- | |- | ||
| [[TSPLIB (Minimum TSP The Traveling-Salesman Problem)|TSPLIB]] || 1991 || $O({2}^V | | [[TSPLIB (Minimum TSP The Traveling-Salesman Problem)|TSPLIB]] || 1991 || $O({2}^V \log E)$ || || Exact || Deterministic || [https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.376 Time] | ||
|- | |- | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:The Traveling-Salesman Problem - Minimum TSP - Time.png|1000px]] | [[File:The Traveling-Salesman Problem - Minimum TSP - Time.png|1000px]] | ||
Latest revision as of 09:09, 28 April 2023
Description
In Minimum TSP, you are given a set $C$ of cities and distances between each distinct pair of cities. The goal is to find an ordering or tour of the cities, such that you visit each city exactly once and return to the origin city, that minimizes the length of the tour. This is the typical variation of TSP.
Related Problems
Related: Maximum TSP, Approximate TSP
Parameters
$V$: number of cities (nodes)
$E$: number of roads (edges)
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Miller-Tucker-Zemlin (MTZ) formulation | 1960 | $exp(V)$ | $O(V^{4})$ | Exact | Deterministic | Time |
| Dantzig-Fulkerson-Johnson (DFJ) formulation | 1954 | $O({1.674}^V E^{2})$ | $O({2}^V)$ | Exact | Deterministic | Time & Space |
| Johnson; D. S.; McGeoch; L. A. | 1997 | $O({2}^{(p(n)$}) | Deterministic | Time | ||
| Gutina; Gregory; Yeob; Anders; Zverovich; Alexey | 2002 | - | Deterministic | Time | ||
| Held–Karp algorithm | 1962 | $O(V^{2} {2}^V)$ | $O(V*{2}^V)$ | Exact | Deterministic | Time |
| Lawler; E. L. | 1985 | $O({1.674}^V E^{2})$ | Exact | Deterministic | Time | |
| TSPLIB | 1991 | $O({2}^V \log E)$ | Exact | Deterministic | Time |
Time Complexity Graph
