A robust 2-stage version for the STEINER TREE problem
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Algorithmic Aspects of Topology Control Problems for Ad Hoc NetworksMobile Networks and Applications, 2005
- An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design2004
- A branch and bound algorithm for the robust shortest path problem with interval dataOperations Research Letters, 2004
- Distributed Construction of Connected Dominating Set in Wireless Ad Hoc NetworksMobile Networks and Applications, 2004
- On the complexity of a class of combinatorial optimization problems with uncertaintyMathematical Programming, 2001
- Robust Discrete Optimization and Its Applications.Journal of the Operational Research Society, 1998
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on NetworksSIAM Journal on Computing, 1995
- Shortest path problems with node failuresNetworks, 1992
- The probabilistic minimum spanning tree problemNetworks, 1990