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

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.
978-3-642-32588-5
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11388/50458
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 5
social impact