Reoptimization of minimum and maximum traveling salesman's tours
Ausiello, Giorgio; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2006), Reoptimization of minimum and maximum traveling salesman's tours, in Arge, Lars; Freivalds, Rusins, Algorithm Theory - SWAT 2006 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, Springer : Berlin, p. 196-207. http://dx.doi.org/10.1007/11785293_20
TypeCommunication / Conférence
Conference title10th Scandinavian Workshop on Algorithm Theory (SWAT 2006)
Book titleAlgorithm Theory - SWAT 2006 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings
Book authorArge, Lars; Freivalds, Rusins
Series titleLecture Notes in Computer Science
Number of pages436
MetadataShow full item record
Abstract (EN)In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.
Subjects / KeywordsReoptimization; Traveling Salesman
Showing items related by title and author.