Improved Approximations for TSP with Simple Precedence Constraints
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)
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
approximation, traveling salesman problem
IdentifiersURN: urn:nbn:se:kth:diva-52382DOI: 10.1007/978-3-642-13073-1ISBN: 978-3-642-13072-4OAI: oai:DiVA.org:kth-52382DiVA: diva2:466356
International Conference on Algorithms and Complexity (CIAC)
ProjectsSNF grant 200021-132510/1
QC 201201132011-12-152011-12-152012-01-13Bibliographically approved