Thumbnail

Reoptimization of minimum and maximum traveling salesman's tours

Ausiello, Giorgio; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2009), Reoptimization of minimum and maximum traveling salesman's tours, Journal of Discrete Algorithms, 7, 4, p. 453-463. http://dx.doi.org/10.1016/j.jda.2008.12.001

View/Open
Type
Article accepté pour publication ou publié
Date
2009
Journal name
Journal of Discrete Algorithms
Volume
7
Number
4
Publisher
Elsevier
Pages
453-463
Publication identifier
Metadata
Show full item record
Author(s)
Ausiello, Giorgio
Escoffier, Bruno
Monnot, Jérôme cc
Paschos, Vangelis
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 / Keywords
Optimisation