• 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

Steiner forests on stochastic metric graphs

Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007), Steiner forests on stochastic metric graphs, in Dress, Andreas; Xu, Yinfeng; Zhu, Binhai, Combinatorial Optimization and Applications First International Conference, COCOA 2007, Xi'an, China, August 14-16, 2007, Proceedings, Springer : Berlin, p. 112-123. http://dx.doi.org/10.1007/978-3-540-73556-4_14

View/Open
steiner_forests.PDF (326.8Kb)
Type
Communication / Conférence
Date
2007
Conference title
First International Conference on Combinatorial Optimization and Applications (COCOA'07)
Conference date
2007-08
Conference city
Xi'an
Conference country
Chine
Book title
Combinatorial Optimization and Applications First International Conference, COCOA 2007, Xi'an, China, August 14-16, 2007, Proceedings
Book author
Dress, Andreas; Xu, Yinfeng; Zhu, Binhai
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4616
Published in
Berlin
ISBN
978-3-540-73555-7
Number of pages
390
Pages
112-123
Publication identifier
http://dx.doi.org/10.1007/978-3-540-73556-4_14
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Telelis, Orestis
Zissimopoulos, Vassilis
Abstract (EN)
We consider the problem of connecting given vertex pairs over a stochastic metric graph, each vertex of which has a probability of presence independently of all other vertices. Vertex pairs requiring connection are always present with probability 1. Our objective is to satisfy the connectivity requirements for every possibly materializable subgraph of the given metric graph, so as to optimize the expected total cost of edges used. This is a natural problem model for cost-efficient Steiner Forests on stochastic metric graphs, where uncertain availability of intermediate nodes requires fast adjustments of traffic forwarding. For this problem we allow a priori design decisions to be taken, that can be modified efficiently when an actual subgraph of the input graph materializes. We design a fast (almost linear time in the number of vertices) modification algorithm whose outcome we analyze probabilistically, and show that depending on the a priori decisions this algorithm yields 2 or 4 approximation factors of the optimum expected cost. We also show that our analysis of the algorithm is tight.
Subjects / Keywords
approximation; Algorithms; Steiner forests; Graphs

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
    A robust 2-stage version for the Steiner tree problem 
    Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007) Document de travail / Working paper
  • Thumbnail
    Approximating the optimal solutions of some hard graph problems by a Boltzmann machine 
    Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1993) Article accepté pour publication ou publié
  • Thumbnail
    The antennas preassignment problem 
    Paschos, Stratos; Paschos, Vangelis; Zissimopoulos, Vassilis (2004) Article accepté pour publication ou publié
  • Thumbnail
    A simulated annealing approach for the circular cutting problem 
    Zissimopoulos, Vassilis; Hifi, Mhand; Paschos, Vangelis (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