Change search
ReferencesLink to record
Permanent link

Direct link
Improved Inapproximability for TSP
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)In: Computing Research Repository, Vol. abs/1206.2497Article in journal (Refereed) Published
Abstract [en]

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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-112879OAI: diva2:587533

QC 20130502

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2013-05-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Search in DiVA

By author/editor
Lampis, Michael
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 39 hits
ReferencesLink to record
Permanent link

Direct link