کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333167 | 688607 | 2009 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reoptimization of minimum and maximum traveling salesman's tours
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 453-463
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 453-463
نویسندگان
Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, Vangelis Paschos,