Minimum TSP (The Traveling-Salesman Problem)

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

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination