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 sharpened triangle inequality
ETH Zurich.
ETH Zurich.
ETH Zurich.
ETH Zurich.
Show others and affiliations
2011 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675Article in journal (Refereed) Published
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 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 polynomialtime 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
Elsevier, 2011.
Keyword [en]
Steiner tree problem, hardness, reoptimization
National Category
Computer and Information Science Natural Sciences Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-60838DOI: 10.1016/j.jda.2011.03.014Scopus ID: 2-s2.0-84856864338OAI: oai:DiVA.org:kth-60838DiVA: diva2:478009
Conference
7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010
Note

QC 20150727

Available from: 2012-01-15 Created: 2012-01-15 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopushttp://www.sciencedirect.com/science/article/pii/S1570866711000499

Search in DiVA

By author/editor
Mömke, Tobias
In the same journal
Journal of Discrete Algorithms
Computer and Information ScienceNatural SciencesComputer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 32 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