Improved Inapproximability for TSP
2012 (English)In: Computing Research Repository, Vol. abs/1206.2497Article in journal (Refereed) Published
The Traveling Salesman Problem is one of the most studied problems incomputational complexity and its approximability has been a long standing openquestion. Currently, the best known inapproximability threshold known is220/219 due to Papadimitriou and Vempala. Here, using an essentially differentconstruction and also relying on the work of Berman and Karpinski on boundedoccurrence CSPs, we give an alternative and simpler inapproximability proofwhich improves the bound to 185/184.
Place, publisher, year, edition, pages
2012. Vol. abs/1206.2497
IdentifiersURN: urn:nbn:se:kth:diva-112879OAI: oai:DiVA.org:kth-112879DiVA: diva2:587533
QC 201305022013-01-142013-01-142013-05-02Bibliographically approved