带区间数据的最小风险斯坦纳树问题

考虑了在带区间数据的不确定网络中, 最小风险和模型以及最小最大风险模型下的斯坦纳树问题. 它们推广了相应模型下的最短路问题和最小支撑树问题, 在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法, 并对算法性能做了理论分析和证明. 结果显示我们的算法具有优良的常数逼近的性质, 能在多项式时间内算出令人满意的解.

THE MINIMUM STEINER TREE PROBLEMS WITH INTERVAL DATA

Based on the models of minimum risk sum and minimum maximum risk, this paper is concerned with the minimum Steiner tree problems in uncertain networks with interval data. Generalizing the shortest path problem and the minimum spanning tree problem in the cresponding risk models, these minimum risk Steiner tree problems have wider real-world applications in network design. The approximation algorithms of the Steiner tree problems in these two models is presented. Finally, the constant approximation ratios of the algorithms are theoretically analyzed and proved.