Minimum TSP

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.

Parameters

$V$ : number of cities (nodes)
$E$ : number of roads (edges)

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms


Held–Karp algorithm	1962	$O(V^2 2^V)$	$O(V 2^V)$
Miller-Tucker-Zemlin (MTZ) formulation	1960	$\text{exp}(V)$	$O(V^4)$
Dantzig-Fulkerson-Johnson (DFJ) formulation	1954	$O(\text{exp}(V))$	$O(V^2 2^V)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms