Date
2007
Collection title
Lecture Notes in Computer Science
Collection Id
4616
Dewey
Recherche opérationnelle
Sujet
approximation; Algorithms; Steiner forests; Graphs
Conference name
First International Conference on Combinatorial Optimization and Applications (COCOA'07)
Conference date
08-2007
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
Author
Dress, Andreas; Xu, Yinfeng; Zhu, Binhai
Publisher
Springer
Publisher city
Berlin
Year
2007
Pages number
390
ISBN
978-3-540-73555-7
Author
Paschos, Vangelis
Telelis, Orestis
Zissimopoulos, Vassilis
Type
Communication / Conférence
Item number of pages
112-123
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.