# Minimum TSP (The Traveling-Salesman Problem)

Jump to navigation
Jump to search

## 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 |