کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430634 | 688072 | 2010 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Reoptimization of the metric deadline TSP Reoptimization of the metric deadline TSP](/preview/png/430634.png)
The reoptimization version of an optimization problem deals with the following scenario: Given an input instance together with an optimal solution for it, the objective is to find a high-quality solution for a locally modified instance.In this paper, we investigate several reoptimization variants of the traveling salesman problem with deadlines in metric graphs (Δ-DlTSP). The objective in the Δ-DlTSP is to find a minimum-cost Hamiltonian cycle in a complete undirected graph with a metric edge cost function which visits some of its vertices before some prespecified deadlines. As types of local modifications, we consider insertions and deletions of a vertex as well as of a deadline.We prove the hardness of all of these reoptimization variants and give lower and upper bounds on the achievable approximation ratio which are tight in most cases.
Journal: Journal of Discrete Algorithms - Volume 8, Issue 1, March 2010, Pages 87–100