Reoptimization of Steiner trees: Changing the terminal set

被引：17

作者：

Boeckenhauer, Hans-Joachim ^{[1
]}

Hromkovic, Juraj ^{[1
]}

Kralovic, Richard ^{[1
]}

Moemke, Tobias ^{[1
]}

Rossmanith, Peter ^{[2
]}

机构：

[1] Swiss Fed Inst Technol, Dept Comp Sci, CH-8092 Zurich, Switzerland

[2] Rhein Westfal TH Aachen, Dept Comp Sci, Aachen, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 36期

关键词：

Approximation algorithms; Reoptimization; Steiner tree;

D O I：

10.1016/j.tcs.2008.04.039

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given an instance of the Steiner tree problem together with an optimal solution, we consider the scenario where this instance is modified locally by adding one of the vertices to the terminal set or removing one vertex from it. In this paper, we investigate the problem of whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. Our results are as follows: (i) We prove that these reoptimization variants of the Steiner tree problem are NP-hard, even if edge costs are restricted to values from {1, 2}. (ii) We design 1.5-approximation algorithms for both variants of local modifications. This is an improvement over the currently best known approximation algorithm for the classical Steiner tree problem which achieves an approximation ratio of 1 + ln(3)/2 approximate to 1.55. (iii) We present a PTAS for the Subproblem in which the edge costs are natural numbers {1,... k} for some constant k. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：3428 / 3435

页数：8