Maximum TSP: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(One intermediate revision 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 22: Line 22:
|-
|-


| [[Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem)|Barvinok]] || 2003 || $O(V^{2} \log\log E)$ || $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]
|-
|-

Latest revision as of 08:22, 10 April 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} \log\log E)$ $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

References/Citation

https://dl.acm.org/doi/pdf/10.1145/876638.876640