New Advances in Reoptimizing the Minimum Steiner Tree Problem

Abstract In this paper we improve the results in the literature concerning the problem of computing the minimum Steiner tree given the minimum Steiner tree for a similar problem instance. Using a σ -approximation algorithm computing the minimum Steiner tree from scratch, we provide a \(\left(\frac{3 \sigma-1}{2 \sigma-1}+\epsilon\right)\) and a \(\left(\frac{2 \sigma-1}{\sigma}+\epsilon\right)\) -approximation algorithm for altering the instance by removing a vertex from the terminal set and by increasing the cost of an edge, respectively. If we use the best up to date σ = ln 4 + ε, our ratios equal 1. 218 and 1. 279 respectively.

Authors

• Davide Bilò
• Anna Zych

Keywords

No keywords are indexed for this paper.