Probabilistic models for the Steiner Tree problem
Probabilistic models for the Steiner Tree problem
复制标题
DOI：
10.1002/net.20346
复制
发表时间：
2010-08
期刊：
影响因子：
2.1
通讯作者：
Vangelis Th. Paschos;Orestis Telelis;V. Zissimopoulos
中科院分区：
文献类型：
--
作者：
Vangelis Th. Paschos;Orestis Telelis;V. Zissimopoulos
我们考虑一个斯坦纳树问题的概率模型。在该模型下，问题被定义为在第一阶段完全加权图上的两阶段设置，其顶点与第二阶段的存在概率相关联（彼此独立）。当图的某些顶点失效时，输入图的第一阶段可行解可能在第二阶段变得不可行。因此，我们设计了一个定义良好的修改策略，用于修改第一阶段解决方案的剩余部分，使其在第二阶段可行。目标是在输入图的所有可能的第二阶段可物化子图的分布上最小化第二阶段解决方案的期望权重。在这种情况下，我们认识到两个互补的计算问题，一个是给定特定修正策略的第一阶段决策的先验计算，另一个是第一阶段可行解决方案的成本效率修正。在这种情况下，我们证明了这两个问题对于Steiner树问题都是NP困难的。我们从概率上设计和分析了一种有效的修正策略，并得到了上述两个问题的严密逼近结果。我们表明，我们的技术可以扩展到更一般的斯坦纳森林问题的情况下，在相同的概率设置。©2009 Wiley期刊公司网络,2010
We consider a probabilistic model for the Steiner Tree problem. Under this model, the problem is defined in a two‐stage setting over a first‐stage complete weighted graph having its vertices associated with a probability of presence (independently each from another) 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. Therefore, a well defined modification strategy is devised for modifying the remainders of a first‐stage solution to render it second‐stage feasible. The objective is to minimize the expected weight of the second‐stage solution over the distribution of all possible second‐stage materializable subgraphs of the input graph. We recognize two complementary computational problems in this setting, one being the a priori computation of first‐stage decisions given a particular modification strategy, and the second being the cost‐efficient modification of a first‐stage feasible solution. We prove that both these problems are NP‐hard for the Steiner Tree problem under this setting. We design and analyze probabilistically an efficient modification strategy and derive tight approximation results for both aforementioned problems. We show that our techniques can be extended to the case of the more general Steiner Forest problem in the same probabilistic setting. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010