The prize-collecting call control problem on weighted lines and rings
The prize-collecting call control problem on weighted lines and rings
复制标题
加权线和环上的收奖呼叫控制问题
DOI：
10.1051/ro/2015010
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yaomin Shi
中科院分区：
文献类型：
--
作者：
Weidong Li;Jianping Li;Li Guan;Yaomin Shi
给定一组具有不同需求和惩罚代价的请求呼叫，奖励收集呼叫控制（Prize-Collecting Call Control，PCCC）问题的目标是最小化边上的最大负载与被拒绝呼叫的总惩罚代价之和.本文证明了带权线路上的PCCC问题在特殊情况下也是NP难的，并利用随机舍入技术设计了一个1.582近似算法。此外，我们还考虑了加权线和加权环上的PCCC问题的一些特殊情况
Given a set of request calls with different demands and penalty costs, the prize-collecting call control (PCCC) problem is to minimize the sum of the maximum load on the edges and the total penalty cost of the rejected calls. In this paper, we prove that the PCCC problem on weighted lines is NP-hard even for special cases, and design a 1.582-approximation algorithm using a randomized.rounding technique. In addition, we consider some special cases of the PCCC problem on weighted lines and rings