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).
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)