Minimum TSP (The Traveling-Salesman Problem)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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

The Traveling-Salesman Problem - Minimum TSP - Time.png