کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431319 | 688504 | 2012 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Steiner tree reoptimization in graphs with sharpened triangle inequality Steiner tree reoptimization in graphs with sharpened triangle inequality](/preview/png/431319.png)
In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β -triangle inequality. A reoptimization algorithm exploits the knowledge of an optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and 1+γ1+γ for an arbitrary small γ>0γ>0), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them.As for the upper bounds, for some local modifications, we design linear-time (1/2+β)(1/2+β)-approximation algorithms, and even polynomial-time approximation schemes, whereas for metric graphs (β=1)(β=1), none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a 2β -approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any β<1/2+ln(3)/4≈0.775β<1/2+ln(3)/4≈0.775.
Journal: Journal of Discrete Algorithms - Volume 11, February 2012, Pages 73–86