Stochastic Steiner Trees Without a Root
Stochastic Steiner Trees Without a Root
复制标题
无根随机斯坦纳树
DOI：
10.1007/11523468_85
复制
发表时间：
2005
影响因子：
2.7
通讯作者：
Martin Pál
中科院分区：
文献类型：
--
作者：
Anupam Gupta;Martin Pál
本文考虑了识别的两阶段随机优化模型中的施泰纳树问题。在不确定性的情况下解决，我们已经做出了仅仅知道森林的决定（而不是确切的需求集）；
在图G =（v，e）上的随机施泰纳树问题的上下文中，该模型可以通过这样的解释：在星期一，我们在顶点的子集上获得了概率分布π，并且可以构建边缘的某些子集EM 。解决方案。
就我们所知，我们为此问题提供了第一个恒定的近似算法。我们认为的Steiner树问题足够强大，可以解决多商品租赁或购买的问题，本身就是最近感兴趣的话题[3,7,15]。
This paper considers the Steiner tree problem in the model of two-stage stochastic optimization with recourse. This model, the focus of much recent research [11, 16, 8, 18], tries to capture the fact that many infrastructure planning problems have to be solved in the presence of uncertainty, and that we have make decisions knowing merely market forecasts (and not the precise set of demands); by the time the actual demands arrive, the costs may be higher due to inflation.
In the context of the Stochastic Steiner Tree problem on a graph G = (V,E), the model can be paraphrased thus: on Monday, we are given a probability distribution π on subsets of vertices, and can build some subset EM of edges. On Tuesday, a set of terminals D materializes (drawn from the same distribution π). We now have to buy edges ET so that the set EM ∪ ET forms a Steiner tree on D. The goal is to minimize the expected cost of the solution.
We give the first constant-factor approximation algorithm for this problem. To the best of our knowledge, this is the first O(1)-approximation for the stochastic version of a non sub-additive problem. In fact, algorithms for the unrooted stochastic Steiner tree problem we consider are powerful enough to solve the Multicommodity Rent-or-Buy problem, itself a topic of recent interest [3, 7, 15].