The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality (Extended Abstract)
Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovic̆, Tobias Mömke, Andreas Sprock, Björn Steffen · 2010
In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β-triangle in- equality. A reoptimization algorithm exploits the knowledge of an opti- mal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened trian- gle inequality (and even in graphs wher e edge-costs are restricted to the values 1 and 1 + γ for an arbitrary small γ> 0), Steiner tree reoptimiza- tion 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+ β)-approximation algorithms, and even polynomial- time approximation schemes, whereas for metric graphs (β = 1), none of these reoptimization variants is known to permit a PTAS. As a build- ing 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+l n(3)/4 ≈ 0.775.