恢复鲁棒带惩罚费用的呼叫控制问题
|
摘要
基于带惩罚费用的呼叫控制问题,进一步讨论恢复鲁棒带惩罚费用的呼叫控制问题,并设计出一个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,.
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,.
引文
[1]Azar Y,Regev O.Combinatorial algorithms for the unsplittable flow problem[J].Algorithmica,2006,44(1):49-66.DOI:10.1007/s00453-005-1172-z.
[2]Li W D,Li J P,Guan L,et al.The prize-collecting call control problem on weighted lines and rings[J].RAIRO-Operations Research,2016,50(1):39-46.DOI:10.1051/ro/2015010.
[3]Li W D,Li J P,Guan L.Approximation algorithms for the ring loading problem with penalty cost[J].Information Processing Letters,2014,114(1-2):56-59.DOI:10.1016/j.ipl.2013.08.004.
[4]陈智斌,李建平.环上的最大流通量问题[J].云南大学学报:自然科学版,2004,26(4):288-291.Chen Z B,Li J P.Maximize the throughput of ring routing problem in SONET[J].Journal of Yunnan University:Natural Sciences Edition,2004,26(4):288-291.
[5]Guan L,Li J,Zhang X,et al.The directed ring loading with penalty cost[C].International Workshop on Algorithms and Computation,Springer,Cham,2015.
[6]Ben-Tal A,El Ghaoui L,Nemirovski A.Robust optimization[M].Princeton:Princeton University Press,2009.
[7]王科.信息不确定条件下的鲁棒数据包络分析建模[J].云南大学学报:自然科学版,2013,35(2):146-154.Wang K.Robust data envelopment analysis modeling under uncertain information[J].Journal of Yunnan University:Natural Sciences Edition,2013,35(2):146-154.
[8]Jordi P.The robust(minmax regret)assembly line worker assignment and balancing problem[J].Computers and Operations Research,2018,93:27-40.DOI:10.1016/j.cor.2018.01.009.
[9]Jordi P.The robust(minmax regret)single machine scheduling with interval processing times and total weighted completion time objective[J].Computers and Operations Research,2016,66:141-152.DOI:10.1016/j.cor.2015.08.010.
[10]Jordi P,Igor A.The robust set covering problem with interval data[J].Annals Operations Research,2013,207(1):217-235.DOI:10.1007/s10479-011-0876-5.
[11]Geoffrion A M.Generalized Benders decomposition[J].Journal of Optimization Theory and Applications,1972,10(4):237-260.DOI:10.1007/BF00934810.
[12]Sotskov Y N,Egorova N G.Single machine scheduling problem with interval processing times and total completion time objective[J].Algorithms,2018,11(5):66.DOI:10.3390/a11050066.
[13]Liebchen C,Lüsing M,M?hring R H,et al.Recoverable robustness[J].ARRIVAL-Project-Technical Report,2007:66.
[14]Büsing C,Koster A M,Kutschka M.Recoverable robust knapsacks:the discrete scenario case[J].Optimization Letters,2011,5(3):379-392.DOI:10.1007/s11590-011-0307-1.
[15]Korte B,Vygen J.Combinatorial Optimization:Theory and Algorithms[M].Berlin:Springer-Verlag Berlin Heidelberg,2005.
[16]Arora S,Barak B,Booksx I.Computational Complexity:a Modern Approach[M].London:Cambridge University Press,2009.
[17]Stoef J M J.Recoverable robustness in scheduling problems[D].Holand:Universiteit Utrecht,2015.
[18]Williamson D P,Shmoys D B.The Design of Approximation Algorithms[M].London:Cambridge University Press,2011.
[2]Li W D,Li J P,Guan L,et al.The prize-collecting call control problem on weighted lines and rings[J].RAIRO-Operations Research,2016,50(1):39-46.DOI:10.1051/ro/2015010.
[3]Li W D,Li J P,Guan L.Approximation algorithms for the ring loading problem with penalty cost[J].Information Processing Letters,2014,114(1-2):56-59.DOI:10.1016/j.ipl.2013.08.004.
[4]陈智斌,李建平.环上的最大流通量问题[J].云南大学学报:自然科学版,2004,26(4):288-291.Chen Z B,Li J P.Maximize the throughput of ring routing problem in SONET[J].Journal of Yunnan University:Natural Sciences Edition,2004,26(4):288-291.
[5]Guan L,Li J,Zhang X,et al.The directed ring loading with penalty cost[C].International Workshop on Algorithms and Computation,Springer,Cham,2015.
[6]Ben-Tal A,El Ghaoui L,Nemirovski A.Robust optimization[M].Princeton:Princeton University Press,2009.
[7]王科.信息不确定条件下的鲁棒数据包络分析建模[J].云南大学学报:自然科学版,2013,35(2):146-154.Wang K.Robust data envelopment analysis modeling under uncertain information[J].Journal of Yunnan University:Natural Sciences Edition,2013,35(2):146-154.
[8]Jordi P.The robust(minmax regret)assembly line worker assignment and balancing problem[J].Computers and Operations Research,2018,93:27-40.DOI:10.1016/j.cor.2018.01.009.
[9]Jordi P.The robust(minmax regret)single machine scheduling with interval processing times and total weighted completion time objective[J].Computers and Operations Research,2016,66:141-152.DOI:10.1016/j.cor.2015.08.010.
[10]Jordi P,Igor A.The robust set covering problem with interval data[J].Annals Operations Research,2013,207(1):217-235.DOI:10.1007/s10479-011-0876-5.
[11]Geoffrion A M.Generalized Benders decomposition[J].Journal of Optimization Theory and Applications,1972,10(4):237-260.DOI:10.1007/BF00934810.
[12]Sotskov Y N,Egorova N G.Single machine scheduling problem with interval processing times and total completion time objective[J].Algorithms,2018,11(5):66.DOI:10.3390/a11050066.
[13]Liebchen C,Lüsing M,M?hring R H,et al.Recoverable robustness[J].ARRIVAL-Project-Technical Report,2007:66.
[14]Büsing C,Koster A M,Kutschka M.Recoverable robust knapsacks:the discrete scenario case[J].Optimization Letters,2011,5(3):379-392.DOI:10.1007/s11590-011-0307-1.
[15]Korte B,Vygen J.Combinatorial Optimization:Theory and Algorithms[M].Berlin:Springer-Verlag Berlin Heidelberg,2005.
[16]Arora S,Barak B,Booksx I.Computational Complexity:a Modern Approach[M].London:Cambridge University Press,2009.
[17]Stoef J M J.Recoverable robustness in scheduling problems[D].Holand:Universiteit Utrecht,2015.
[18]Williamson D P,Shmoys D B.The Design of Approximation Algorithms[M].London:Cambridge University Press,2011.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |