Change search
ReferencesLink to record
Permanent link

Direct link
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, 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
URN: urn:nbn:se:kth:diva-41948DOI: 10.1016/j.tcs.2008.04.039ISI: 000269097800011OAI: diva2:445604
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: 2012-01-15Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full text

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: 282 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

Altmetric score

Total: 41 hits
ReferencesLink to record
Permanent link

Direct link