Maximum TSP (The Traveling-Salesman Problem)

From Algorithm Wiki
Revision as of 08:22, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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


$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