Approximate 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


Approximate TSP is the problem of finding an approximate answer to 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.

Related Problems

Related: Minimum TSP, Maximum TSP


$V$: number of cities (nodes)

$E$: number of roads (edges)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Applegate et al. 2006 $O(V^{2} E)$ Deterministic Time
Johnson; D. S.; McGeoch; L. A. 1997 $O({2}^{(p(n)$}) Deterministic Time
Gutina; Gregory; Yeob; Anders; Zverovich; Alexey 2002 - Deterministic Time
Rosenkrantz; D. J.; Stearns; R. E.; Lewis; P. M. 1974 $O(V^{2})$ $O({1})$ 1/2\log n + 1/2 Deterministic Time
Lin–Kernighan 1981 $O(V^{2})$ $O(V)$ Deterministic Time & Space
Christofides algorithm 1976 $O(V^{3})$ $O(V^{2})$??? 1.5 Deterministic Time