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

Recoverable robust prize-collecting call control problem

作　　者：黄彦 李建平[1] HUANG Yan;LI Jian-ping(School of Mathematics and Statistics, Yunnan University, Kunming 650091, Yunnan)

机构地区：[1]云南大学数学与统计学院

出　　处：《云南大学学报（自然科学版）》2019年第4期661-668,共8页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金(11861075);云南省科学技术厅——云南大学联合重点项目(2018FY001(-014));云南省高校科技创新团队支持计划资助

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

关 键 词：恢复鲁棒 呼叫控制 近似算法 动态规划算法 全多项式时间近似方案 

分 类 号：O224[理学—运筹学与控制论]