Simple and fast reoptimizations for the steiner tree problem

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:	3386
Downloads:	27
Metadata:
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Language:	Unknown
Keywords:	Steiner tree, approximation algorithms, reoptimization

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back