Maximum TSP: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 22: | Line 22: | ||
|- | |- | ||
| [[Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem)|Barvinok]] || 2003 || $O(V^{2} loglogE)$ || $O(V)$? || ? || Deterministic || [https://dl.acm.org/doi/10.1145/876638.876640 Time] | |||
|- | |||
| [[Johnson; D. S.; McGeoch; L. A. ( The Traveling-Salesman Problem)|Johnson; D. S.; McGeoch; L. A.]] || 1997 || $O({2}^{(p(n)$}) || || || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf Time] | | [[Johnson; D. S.; McGeoch; L. A. ( The Traveling-Salesman Problem)|Johnson; D. S.; McGeoch; L. A.]] || 1997 || $O({2}^{(p(n)$}) || || || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf Time] | ||
|- | |- | ||
Revision as of 13:04, 15 February 2023
Description
In Maximum 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 maximizes the length of the tour.
Related Problems
Related: Minimum 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 |
|---|---|---|---|---|---|---|
| Barvinok | 2003 | $O(V^{2} loglogE)$ | $O(V)$? | ? | Deterministic | Time |
| Johnson; D. S.; McGeoch; L. A. | 1997 | $O({2}^{(p(n)$}) | Deterministic | Time | ||
| Gutina; Gregory; Yeob; Anders; Zverovich; Alexey | 2002 | - | Deterministic | Time |