Change search
ReferencesLink to record
Permanent link

Direct link
The Steiner tree reoptimization problem with sharpenedtriangle inequality
ETH Zurich.
ETH Zurich.
ETH Zurich.
ETH Zurich.
Show others and affiliations
2010 (English)Conference paper (Refereed)
Abstract [en]

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
Keyword [en]
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
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-59784DOI: 10.1007/978-3-642-13073-1_17ISI: 000279393400017ScopusID: 2-s2.0-77953775509ISBN: 978-364213072-4ISBN: 3642130720OAI: diva2:476316
7th International Conference on Algorithms and Complexity, CIAC-2010, Rome, 26 May 2010 through 28 May 2010

QC 20120113

Available from: 2012-01-11 Created: 2012-01-11 Last updated: 2016-05-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Mömke, Tobias
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 27 hits
ReferencesLink to record
Permanent link

Direct link