Approximation hardness of the traveling salesman reoptimization problem
2007 (English)In: Proceedings of the 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007), 2007, 97-104 p.Conference paper (Refereed)
In TSP reoptimization, a complete weighted graph and an optimal Hamiltonian tour are given; the problem is to find an optimal solution for a locally modified input. In this paper, we consider the local modification where one edge of the graph becomes cheaper. We show that the best approximation ratio known so far that is achievable by polynomial-time algorithms heavily depends on various parameters. We show that for a wide range of parameters the approximation ratio is improved. Moreover, these parameters limit the class of hard instances, which might help to find better approximation algorithms also for the general case.
Place, publisher, year, edition, pages
2007. 97-104 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-60839OAI: oai:DiVA.org:kth-60839DiVA: diva2:478017
3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007), October 26-28, 2007, Znojmo, Czech Republic
QC 201201182012-01-152012-01-152016-05-25Bibliographically approved