News for hackers. Stuff that matters.
Re:Subhash Khot and the Unique Games Conjecture by anuragbiyani on Wednesday August 13, 2014 @01:40AM (#8171594)
Actually general version of TSP (optimization problem) cannot be approximated to a constant factor in polynomial time unless P = NP. [1]

Your confusion likely stem from the fact that metric-TSP (a special case of TSP problem where the distance between cities form a metric [2]) is actually APX-complete, which means it can be approximated to a constant factor in polynomial time (Christofides algorithm, approx ratio = 1.5).

PS: A potentially interesting aside - Sanjeev Arora, the PhD advisor of Subhash Khot actually got his first Gödel prize (2001) for discovering a PTAS (polynomial time approximation scheme, which in layman term means you can approximate it as close to real answer (but not exactly) as you like in polynomial time) for Euclidean-TSP (independently discovered by Joseph S. B. Mitchell as well). The algorithm make pretty interesting use of Dynamic programming, and was a surprise for the theoretical CS community that time.

[1] Brief intuition - HAMILTON-PATH (decision version) can be solved exactly in polynomial time using a constant factor poly time approximation of general TSP (optimization). But since, HAMILTON-PATH is proven to be NP-Complete, then P must equal NP (in which case we can solve all problems in NP and their optimization counterparts exactly in polynomial time anyway). For a formal proof see Khot's lecture notes: http://www.cs.nyu.edu/~khot/lec1.ps (you can find a variety of other similar resources as well, as this is one of the first impossibility proof in almost any graduate level approximation algorithm class).

[2] http://en.wikipedia.org/wiki/Metric_(mathematics)

There are no comments on this comment yet.