A robust 2-stage version for the Steiner tree problem

Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis

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

Type

Document de travail / Working paper

External document link

http://hal.archives-ouvertes.fr/hal-00180537/en/

Date

2007

Publisher

Université Paris-Dauphine

Series title

Annales du LAMSADE

Series number

Published in

Paris

Metadata

Show full item record

Author(s)

Paschos, Vangelis
Telelis, Orestis
Zissimopoulos, Vassilis

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