Show simple item record

A robust 2-stage version for the Steiner tree problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis
hal.structure.identifierDepartment of Informatics and Telecomunications [Kapodistrian Univ] [DI NKUA]
dc.contributor.authorTelelis, Orestis
hal.structure.identifierDepartment of Informatics and Telecomunications [Kapodistrian Univ] [DI NKUA]
dc.contributor.authorZissimopoulos, Vassilis
dc.date.accessioned2011-07-29T14:34:31Z
dc.date.available2011-07-29T14:34:31Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6852
dc.descriptionp. 191-207en
dc.description.abstractfrDans cet article, nous considérons une version robuste pour l’arbre de Steiner. Sous cette version, le problème est défini dans un cadre en deux étapes sur un graphe complet à arêtes pondérées dont les sommets sont associés avec des probabilités de présence en seconde étape. Une solution réalisable pour la première étape sur le graphe d’entrée peut devenir non-réalisable pour la seconde étape, quand quelques sommets disparaissent. Dans ce cas, une « stratégie de modification » est conçue qui transforme une solution partielle en une solution réalisable pour la seconde étape. L’objectif est de concevoir un algorithme qui calcul une solution pour la première étape (cette solution s’appelle solution a priori ou « d’anticipation ») de qui minimise la fonction objectif du problème robuste. Une caractéristique importante de ce modèle robuste est que la stratégie de modification est partie du problème. Nous recherchons de résultats de complexité et d’approximation en utilisant une stratégie de modification basée sur l’algorithme du parcours en profondeur.en
dc.language.isoenen
dc.subjectRobustesseen
dc.subjectOptimisation probabilisteen
dc.subjectGraphesen
dc.subjectcomplexitéen
dc.subjectArbre de Steineren
dc.subjectSteiner treeen
dc.subjectRobustnessen
dc.subjectProbabilistic optimizationen
dc.subjectGraphsen
dc.subjectComplexityen
dc.subjectApproximationen
dc.subject.ddc003en
dc.titleA robust 2-stage version for the Steiner tree problemen
dc.typeDocument de travail / Working paper
dc.description.abstractenIn this paper we consider a robust version for STEINER TREE. Under it, the problem is defined in a two-stage setting over a complete weighted graph whose vertices are associated with a probability of presence in the second stage. A first-stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail (with the specified probability). Therefore, a well defined modification strategy is devised which transforms a partial solution to a feasible second-stage solution. The objective is to devise an algorithm for the first-stage solution (sometimes called the a priori or anticipatory solution) so that the expected second-stage solution cost is minimized. An important feature of this framework is that the modification strategy is essentially a part of the problem, while algorithmic treatment is required in the construction of the anticipatory solution. We provide complexity and approximation results regarding a modification strategy based upon the well known depth-first-search algorithm.en
dc.publisher.nameUniversité Paris-Dauphineen
dc.publisher.cityParisen
dc.identifier.citationpages17en
dc.relation.ispartofseriestitleAnnales du LAMSADEen
dc.relation.ispartofseriesnumber7en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
AN7LAMSADE_191-207.pdf
Size:
264.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record