3 ms·
The general TSP (where negative edge weights are allowed) cannot be efficiently approximated (if not P = NP). The Christofides algorithm considers are far more
by wolfgke 14y ago
The general TSP (where negative edge weights are allowed) cannot be efficiently approximated (if not P = NP).
The Christofides algorithm considers are far more limited version of the TSP problem (whose decision problem is still NP-complete): the so called "metric TSP": here the edge weights form a metric on the arcs, i. e.
d(v, w) > 0 and d(u, v) + d(v, w) >= d(u, w) for all u, v, w pairwise different (where d(v, w) is the weight on the edge {v, w}).
- deleted 14y ago[deleted]
- bhickey 14y agoIf you restrict the metric case even further and only allow planar graphs, you get even some neat approximations. For example, there exists an O(c^(1/e^2)n) epsilon approximation scheme: http://cs.brown.edu/~pnk/publications/tsp2005.pdf http://cs.brown.edu/~pnk/publications/tsp2005.pdf This manuscript, http://planarity.org/ http://planarity.org/ , contains most of the material in a planar graph optimization course I took a few years ago.