黄彦, 李建平. 恢复鲁棒带惩罚费用的呼叫控制问题[J]. 云南大学学报(自然科学版), 2019, 41(4): 661-668. doi: 10.7540/j.ynu.20180790
引用本文: 黄彦, 李建平. 恢复鲁棒带惩罚费用的呼叫控制问题[J]. 云南大学学报(自然科学版), 2019, 41(4): 661-668. doi: 10.7540/j.ynu.20180790
HUANG Yan, LI Jian-ping. Recoverable robust prize-collecting call control problem[J]. Journal of Yunnan University: Natural Sciences Edition, 2019, 41(4): 661-668. DOI: 10.7540/j.ynu.20180790
Citation: HUANG Yan, LI Jian-ping. Recoverable robust prize-collecting call control problem[J]. Journal of Yunnan University: Natural Sciences Edition, 2019, 41(4): 661-668. DOI: 10.7540/j.ynu.20180790

恢复鲁棒带惩罚费用的呼叫控制问题

Recoverable robust prize-collecting call control problem

  • 摘要: 基于带惩罚费用的呼叫控制问题,进一步讨论恢复鲁棒带惩罚费用的呼叫控制问题,并设计出一个1.58-近似算法. 特别地,当赋权线路上边数为2,情景数为2时,设计了一个动态规划算法,最后基于动态规划算法思想,设计出一个全多项式时间近似方案解决该问题.

     

    Abstract: Based on prize-collecting call control problem, the recoverable robust prize-collecting call control problem is further proposed and a 1.58-approximation algorithm for this problem is designed. In particular, when there are two edges on the weighted line and two scenarios, a dynamic programming algorithm is presented, and a fully polynomial time approximation scheme based on dynamic programming algorithm finally designed to solve the problem, .

     

/

返回文章
返回