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: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag , 2012, 243-253 p.Conference paper (Refereed)
Abstract [en]

The Traveling Salesman Problem is one of the most studied problems in computational complexity and its approximability has been a long standing open question. Currently, the best known inapproximability threshold known is 220/219 due to Papadimitriou and Vempala. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to 185/184.

Place, publisher, year, edition, pages
Springer-Verlag , 2012. 243-253 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7408 LNCS
Keyword [en]
Approximability, Inapproximability, Combinatorial optimization, Traveling salesman problem, Approximation algorithms
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-104875DOI: 10.1007/978-3-642-32512-0_21ScopusID: 2-s2.0-84865301246ISBN: 978-364232511-3OAI: diva2:567827
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012, 15 August 2012 through 17 August 2012, Cambridge, MA

QC 20121114

Available from: 2012-11-14 Created: 2012-11-14 Last updated: 2012-11-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lampis, Michail
By organisation
Theoretical Computer Science, TCS
Computer and Information 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

Altmetric score

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link