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 (3σ−12σ−1+ϵ) and a (2σ−1σ+ϵ) -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.
New advances in reoptimizing the minimum Steiner tree problem / Bilò, Davide; Zych, Anna. - 7464:(2012), pp. 184-197. (Intervento presentato al convegno 37th International Symposium on Mathematical Foundations of Computer Science tenutosi a Bratislava, Slovakia nel 27-31 agosto 2012) [10.1007/978-3-642-32589-2_19].
New advances in reoptimizing the minimum Steiner tree problem
BILÒ, Davide;
2012-01-01
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 (3σ−12σ−1+ϵ) and a (2σ−1σ+ϵ) -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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
