• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
AN7LAMSADE_191-207.pdf (264.9Kb)
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

Related items

Showing items related by title and author.

  • Thumbnail
    Probabilistic models for the Steiner Tree problem 
    Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2010) Article accepté pour publication ou publié
  • Thumbnail
    Steiner forests on stochastic metric graphs 
    Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007) Communication / Conférence
  • Thumbnail
    A simulated annealing approach for the circular cutting problem 
    Zissimopoulos, Vassilis; Hifi, Mhand; Paschos, Vangelis (2004) Article accepté pour publication ou publié
  • Thumbnail
    A neural network for the minimum set covering problem 
    Zissimopoulos, Vassilis; Paschos, Vangelis; Hifi, Mhand (2000) Article accepté pour publication ou publié
  • Thumbnail
    The antennas preassignment problem 
    Paschos, Stratos; Paschos, Vangelis; Zissimopoulos, Vassilis (2004) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo