Date
2007
Publisher city
Paris
Publisher
Université Paris-Dauphine
Notes
p. 191-207
Collection title
Annales du LAMSADE
Collection Id
7
Dewey
Recherche opérationnelle
Sujet
Robustesse; Optimisation probabiliste; Graphes; complexité; Arbre de Steiner; Steiner tree; Robustness; Probabilistic optimization; Graphs; Complexity; Approximation
Author
Paschos, Vangelis
Telelis, Orestis
Zissimopoulos, Vassilis
Type
Document de travail / Working paper
Item number of pages
17
Abstract (FR)
Dans 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.
Abstract (EN)
In 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.
