说明:我们研究了代价高昂的有向环加载问题,即选择一些具有不同需求的超边缘表示的给定多播请求,并将其嵌入有向环中,以使环上所有链路与网络之间最大拥塞之和。未选择的多播请求的总代价成本被最小化。 我们证明即使需求是可分割的,这个问题也是NP难的,然后分别针对需求可分割的情况设计了1.582近似算法和针对需求不可分割的情况设计了3近似算法。 因此,对于任何ε> 0的情况,对于每个多播请求都恰好包含一个接收器的情况,我们提出一种(1.582 +ε)近似算法。
<weixin_38535364> 上传 | 大小:512kb