Approximate TSP (The Traveling-Salesman Problem)

Description

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

Parameters

$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