Simple and fast reoptimizations for the steiner tree problem

Escoffier, Bruno; Milanič, Martin; Paschos, Vangelis Th.

SLO

First page / Show document

Show document

A- | A+ | Print

Title:	Simple and fast reoptimizations for the steiner tree problem
Authors:	ID Escoffier, Bruno (Author) ID Milanič, Martin (Author) ID Paschos, Vangelis Th. (Author)
Files:	http://journals.hil.unb.ca/index.php/AOR/article/view/5653
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	IAM - Andrej Marušič Institute
Abstract:	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.
Keywords:	reoptimizacija, Steinerjevo drevo, aproksimacijski algoritem
Year of publishing:	2009
Number of pages:	str. 86-94
Numbering:	Vol. 4, no. 2
PID:	20.500.12556/RUP-943
UDC:	519.85
COBISS.SI-ID:	1024188756
Publication date in RUP:	15.10.2013
Views:	3674
Downloads:	28
Metadata:
:	ESCOFFIER, Bruno, MILANIČ, Martin and PASCHOS, Vangelis Th., 2009, Simple and fast reoptimizations for the steiner tree problem. [online]. 2009. Vol. 4, no. 2, p. 86–94. [Accessed 3 April 2025]. Retrieved from: http://journals.hil.unb.ca/index.php/AOR/article/view/5653 Copy citation