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].
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | New advances in reoptimizing the minimum Steiner tree problem | |
Autori: | ||
Data di pubblicazione: | 2012 | |
Rivista: | ||
Citazione: | 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]. | |
Handle: | http://hdl.handle.net/11388/50458 | |
ISBN: | 978-3-642-32588-5 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |