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 and a -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. © 2012 Springer-Verlag.
Titolo: | New advances in reoptimizing the minimum Steiner tree problem | |
Autori: | ||
Data di pubblicazione: | 2012 | |
Serie: | ||
Handle: | http://hdl.handle.net/11697/179717 | |
ISBN: | 978-3-642-32588-5 978-3-642-32589-2 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.