Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Steiner tree reoptimization problem with sharpenedtriangle inequality
ETH Zurich.
ETH Zurich.
ETH Zurich.
ETH Zurich.
Show others and affiliations
2010 (English)Conference paper, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 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
Identifiers
URN: urn:nbn:se:kth:diva-59784DOI: 10.1007/978-3-642-13073-1_17ISI: 000279393400017Scopus ID: 2-s2.0-77953775509ISBN: 978-3-642-13072-4 (print)OAI: oai:DiVA.org:kth-59784DiVA: diva2:476316
Conference
7th International Conference on Algorithms and Complexity, CIAC-2010, Rome, 26 May 2010 through 28 May 2010
Note

QC 20120113

Available from: 2012-01-11 Created: 2012-01-11 Last updated: 2017-03-24Bibliographically 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf