Approximate TSP: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE: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....") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$V$: number of cities (nodes) | |||
E: number of roads (edges) | |||
$E$: number of roads (edges) | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:22, 10 April 2023
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 |