Thumbnail

A robust 2-stage version for the Steiner tree problem

Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007), A robust 2-stage version for the Steiner tree problem. https://basepub.dauphine.fr/handle/123456789/6852

View/Open
Type
Document de travail / Working paper
Date
2007
Publisher
Université Paris-Dauphine
Series title
Annales du LAMSADE
Series number
7
Published in
Paris
Pages
17
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Telelis, Orestis
Department of Informatics and Telecomunications [Kapodistrian Univ] [DI NKUA]
Zissimopoulos, Vassilis
Department of Informatics and Telecomunications [Kapodistrian Univ] [DI NKUA]
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.
Subjects / Keywords
Robustesse; Optimisation probabiliste; Graphes; complexité; Arbre de Steiner; Steiner tree; Robustness; Probabilistic optimization; Graphs; Complexity; Approximation