The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality
METADATA ONLY
Loading...
Author / Producer
Date
2010
Publication Type
Other Conference Item
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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 + γ for an arbitrary small γ> 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 + β)-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 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.
Permanent link
Publication status
published
External links
Book title
Algorithms and Complexity
Journal / series
Volume
6078
Pages / Article No.
180 - 191
Publisher
Springer
Event
7th International Conference on Algorithms and Complexity (CIAC 2010)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
Notes
Extended Abstract.