The Steiner tree reoptimization problem with sharpenedtriangle inequality
2010 (English)Conference paper (Refereed)
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 theknowledge 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 triangleinequality (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 theupper 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.
Place, publisher, year, edition, pages
2010. Vol. 6078, 180-191 p.
, Lecture Notes in Computer Science, ISSN 03029743 ; 6078
Building blockes, NP-hard, Optimal solutions, Polynomial time approximation schemes, Problem instances, Re-optimization algorithms, Reoptimization, Steiner tree problem, Steiner trees, Triangle inequality, Upper Bound
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-59784DOI: 10.1007/978-3-642-13073-1_17ISI: 000279393400017ScopusID: 2-s2.0-77953775509ISBN: 978-364213072-4ISBN: 3642130720OAI: oai:DiVA.org:kth-59784DiVA: diva2:476316
7th International Conference on Algorithms and Complexity, CIAC-2010, Rome, 26 May 2010 through 28 May 2010
QC 201201132012-01-112012-01-112016-05-25Bibliographically approved