On The Approximability Of The Traveling Salesman Problem

We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than $$ \frac{{117}} {{116}} $$when the edge lengths are allowed to be asymmetric and $$ \frac{{220}} {{219}} $$when the edge lengths are symmetric, unless P=NP. The best previous lower bounds were $$ \frac{{2805}} {{2804}} $$and $$ \frac{{3813}} {{3812}} $$respectively. The reduction is from Håstad’s maximum satisfiability of linear equations modulo 2, and is nonconstructive.We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than $$ \frac{{117}} {{116}} $$when the edge lengths are allowed to be asymmetric and $$ \frac{{220}} {{219}} $$when the edge lengths are symmetric, unless P=NP. The best previous lower bounds were $$ \frac{{2805}} {{2804}} $$and $$ \frac{{3813}} {{3812}} $$respectively. The reduction is from Håstad’s maximum satisfiability of linear equations modulo 2, and is nonconstructive.