• 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

Probabilistic models for the Steiner Tree problem

Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2010), Probabilistic models for the Steiner Tree problem, Networks, 56, 1, p. 39-49. http://dx.doi.org/10.1002/net.20346

View/Open
cahierLamsade254.pdf (429.2Kb)
Type
Article accepté pour publication ou publié
Date
2010
Journal name
Networks
Volume
56
Number
1
Publisher
Wiley
Pages
39-49
Publication identifier
http://dx.doi.org/10.1002/net.20346
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Telelis, Orestis
Zissimopoulos, Vassilis
Abstract (EN)
We consider a probabilistic model for the Steiner Tree problem. Under this model, the problem is defined in a two-stage setting over a first-stage complete weighted graph having its vertices associated with a probability of presence (independently each from another) 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. Therefore, a well defined modification strategy is devised for modifying the remainders of a first-stage solution to render it second-stage feasible. The objective is to minimize the expected weight of the second-stage solution over the distribution of all possible second-stage materializable subgraphs of the input graph. We recognize two complementary computational problems in this setting, one being the a priori computation of first-stage decisions given a particular modification strategy, and the second being the cost-efficient modification of a first-stage feasible solution. We prove that both these problems are NP-hard for the Steiner Tree problem under this setting. We design and analyze probabilistically an efficient modification strategy and derive tight approximation results for both aforementioned problems. We show that our techniques can be extended to the case of the more general Steiner Forest problem in the same probabilistic setting.
Subjects / Keywords
Complexity; Graph; Approximation; Forest; Steiner Tree

Related items

Showing items related by title and author.

  • Thumbnail
    A robust 2-stage version for the Steiner tree problem 
    Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007) Document de travail / Working paper
  • 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