We give an overview of new and existing cut- and flow-based ILP formulations for the two-stage stochastic Steiner tree problem and compare the strength of the LP relaxations.
Although the STP allows constant factor approximations the stochastic problems are harder to approximate. @cite_26 showed that the group Steiner tree problem, which is @math -hard to approximate, can be reduced to the stochastic shortest path problem (a special case of the (r)SSTP). Nevertheless, in literature stochastic versions of the STP have been mostly investigated for approximation algorithms. Due to the inapproximability results restricted versions have been considered to obtain approximation algorithms, e.g., by introducing a fixed and or uniform inflation factor or a global terminal (a vertex being a terminal in all scenarios). Moreover, different models of scenario representations are used. Here, we concentrate on the finite polynomial scenario model where the random variables of the stochastic problems are assumed to have finite support. Other publications consider the black box oracle model. For an overview of these concepts see, e.g., @cite_15 .
@cite_15 @cite_26
168538608 2112058494
This issue’s column is written by guest columnists, David Shmoys and Chaitanya Swamy. Iam delighted that they agreed to write this timely column on the topic related to stochasticoptimization that has received much attention recently. Their column introduces the readerto several recent results and provides references for further readings.Samir Khuller We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios.The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its deterministic counterpart. Furthermore, we show that common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be adapted to obtain these results.