Change search
ReferencesLink to record
Permanent link

Direct link
Improved Approximations for TSP with Simple Precedence Constraints
ETH Zurich.
Laboratoire Bordelais de Recherche en Informatique.
ETH Zurich.
ETH Zurich.
2010 (English)In: Algorithms and Complexity: 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings / [ed] Tiziana Calamoneri, Joesp Diaz, Berlin: Springer Berlin/Heidelberg, 2010, Vol. 6078, 61-72 p.Conference paper (Refereed)
Abstract [en]

Under the usual complexity-theoretic assumptions like P \neq NP, many practically relevant optimization problems are provably hard to solve or even to approximate. But most of these hardness results are derived for worst-case scenarios, and it is in many cases not clear whether the actual problem instances arising in practical applications exhibit this worst-case behaviour. Thus, a recent branch of algorithmic research aims at a more fine-grained analysis of the hardness of optimization problems. The main idea behind this analysis is to find some parameter according to which one can classify the hardness of problem instances. This approach does not only lead to new hardness results, but can also be used to design improved approximation algorithms for practically relevant subclasses of problem instances. In this paper, we survey several different approaches for such improved approximation results achieved by a fine-grained classification of problem instances.

Place, publisher, year, edition, pages
Berlin: Springer Berlin/Heidelberg, 2010. Vol. 6078, 61-72 p.
, Lecture Notes in Computer Science, 6078
Keyword [en]
approximation, traveling salesman problem
National Category
Computer Science
URN: urn:nbn:se:kth:diva-52382DOI: 10.1007/978-3-642-13073-1ISBN: 978-3-642-13072-4OAI: diva2:466356
International Conference on Algorithms and Complexity (CIAC)
SNF grant 200021-132510/1
QC 20120113Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2012-01-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
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

Altmetric score

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link