Experimental Evaluation of Approximation Algorithms for the Minimum Cost Multiple-source Unsplittable Flow Problem
Experimental Evaluation of Approximation Algorithms for the Minimum Cost Multiple-source Unsplittable Flow Problem
复制标题
最小成本多源不可分流问题近似算法的实验评估
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Yasuhito Asano
中科院分区：
文献类型：
--
作者：
Yasuhito Asano
对于最小费用多源不可拆分流问题，提出了一个2-费用（c+ 2）-拥塞近似算法，其中c是不同源的个数。我们还提出了一些基于线性规划松弛与随机舍入和贪婪的方法，并实现所提出的近似算法，并通过计算实验来检查近似的质量。
For the minimum cost multiple-source unsplittable flow problem, we propose a 2-cost and (c+ 2)-congestion approximation algorithm, where c is the number of distinct sources. We also propose some heuristics based on a linear programming relaxation with randomized rounding and a greedy approach, and implement the proposed approximation algorithms and examine the quality of approximation achieved through computational experiments.