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
Reoptimization of Steiner Trees: Changing the Terminal Set
ETH Zurich.
ETH Zurich.
ETH Zurich.
ETH Zurich.
Show others and affiliations
2009 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 410, no 36, 3428-3435 p.Article in journal (Refereed) Published
Abstract [en]

Given an instance of the Steiner tree problem together with an optimalsolution, we consider the scenario where this instance is modifiedlocally by adding one of the vertices to the terminal set or removing onevertex from it. In this paper, we investigate the problem whether theknowledge of an optimal solution to the unaltered instance can help insolving the locally modified instance. Our results are as follows:

- We prove that these reoptimization variants of the Steiner treeproblem are NP-hard, even if edge costs are restricted to values from {1,2}.

- We design 1.5-approximation algorithms for both variants of localmodifications. This is an improvement over the currently best knownapproximation algorithm for the classical Steiner tree problem whichachieves an approximation ratio of 1+ln(3)/2 \approx 1.55.

- We present a PTAS for the subproblem in which the edge costs arenatural numbers {1,...,k} for some constant k.

Place, publisher, year, edition, pages
Elsevier , 2009. Vol. 410, no 36, 3428-3435 p.
Keyword [en]
approximation, reoptimization, Steiner trees
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-41948DOI: 10.1016/j.tcs.2008.04.039ISI: 000269097800011OAI: oai:DiVA.org:kth-41948DiVA: diva2:445604
Note
NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science [VOL410, ISSUE 36, 31 August 2009 DOI10.1016/j.tcs.2008.04.039 QC 20111005Available from: 2011-10-05 Created: 2011-10-04 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

fulltext(154 kB)315 downloads
File information
File name FULLTEXT01.pdfFile size 154 kBChecksum SHA-512
ce121b6452d57678309e95611821db339a2b2911a09a8e02ac1ccba6a1a6c25fec35f969da1255d197b45b85ee6420e28aebb2caccd683bd1e5c8a07a1f1902f
Type fulltextMimetype application/pdf

Other links

Publisher's full texthttp://dx.doi.org/10.1016/j.tcs.2008.04.039

Search in DiVA

By author/editor
Mömke, Tobias
In the same journal
Theoretical Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 315 downloads
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

doi
urn-nbn

Altmetric score

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