Simple and fast reoptimizations for the steiner tree problem

ENG

Prijava

Prva stran / Izpis gradiva

Izpis gradiva

A- | A+ | Natisni

Naslov:	Simple and fast reoptimizations for the steiner tree problem
Avtorji:	ID Escoffier, Bruno (Avtor) ID Milanič, Martin (Avtor) ID Paschos, Vangelis Th. (Avtor)
Datoteke:	http://journals.hil.unb.ca/index.php/AOR/article/view/5653
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	IAM - Inštitut Andrej Marušič
Opis:	We address reoptimization issues for the Steiner tree problem. We assume that an optimal solution is given for some instance of the problem and the objective is to maintain a good solution when the instance is subject to minor modifications, the simplest such modifications being vertex insertions and deletions. We propose fast reoptimization strategies for the case of vertex insertions and we show that maintenance of a good solution for the 'shrunk' instance, without ex nihilo computation, is impossible when vertex deletions occur. We also provide lower bounds for the approximation ratios of the reoptimization strategies studied.
Ključne besede:	reoptimizacija, Steinerjevo drevo, aproksimacijski algoritem
Leto izida:	2009
Št. strani:	str. 86-94
Številčenje:	Vol. 4, no. 2
PID:	20.500.12556/RUP-943
UDK:	519.85
COBISS.SI-ID:	1024188756
Datum objave v RUP:	15.10.2013
Število ogledov:	2997
Število prenosov:	26
Metapodatki:
:	Kopiraj citat