Problem Detail: If $L$ is an APX-hard language, doesn’t the existence of a PTAS for $L$ trivially imply $mathsf{P} = mathsf{NP}$? Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT [1] unless $mathsf{P} = mathsf{NP}$. Thus if there was a PTAS for $L$ we could reduce metric-TSP using a PTAS reduction to $L$ and thus can approximate OPT within arbitrary precision. Is my argument correct? [1] Christos H. Papadimitriou and Santosh Vempala. On the approximability Of the traveling salesman problem. Combinatorica, 26(1):101–120, Feb. 2006.
Asked By : jimmy
Answered By : Tsuyoshi Ito
Some people (including more than one moderators) complained to me for posting an answer based on a comment, and I am tired of defending me from them. I asked them to delete this answer.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3245 Ask a Question Download Related Notes/Documents
