带有多折扣选项的滑雪租赁问题的在线和离线算法
|
摘要
研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.
This paper studies the online and offline algorithms for the ski-rental problem with multiple discount options(multiple- discount ski-rental problem), which is a natural extension of the famous ski-rental problem and has many applications in the real world. In this problem, besides the rental and buy options, there are some other options to rent equipments for a duration with some discount. The longer the duration, the more the discount. A special case of the ski-rental problem with multiple discount options, where for any two options the cost of one is an integral multiple of that of the other one, is called the regular cost subproblem. This study proves the NP-hardness of the off-line version of the ski-rental problem with multiple discount options, and gives a linear algorithm for the regular cost subproblem. Based on the analysis of the off-line problems, it proposes a 2-competitive online algorithm for the regular cost subproblem and proves the optimality of the competitive ratio. Based on the online algorithm of the regular cost subproblem, It presents a 4-competitive online algorithm for the ski-rental problem with multiple discount options that is also optimal. Some experimental results are also given to show the effectiveness of the algorithms when running on some real data and random data.
This paper studies the online and offline algorithms for the ski-rental problem with multiple discount options(multiple- discount ski-rental problem), which is a natural extension of the famous ski-rental problem and has many applications in the real world. In this problem, besides the rental and buy options, there are some other options to rent equipments for a duration with some discount. The longer the duration, the more the discount. A special case of the ski-rental problem with multiple discount options, where for any two options the cost of one is an integral multiple of that of the other one, is called the regular cost subproblem. This study proves the NP-hardness of the off-line version of the ski-rental problem with multiple discount options, and gives a linear algorithm for the regular cost subproblem. Based on the analysis of the off-line problems, it proposes a 2-competitive online algorithm for the regular cost subproblem and proves the optimality of the competitive ratio. Based on the online algorithm of the regular cost subproblem, It presents a 4-competitive online algorithm for the ski-rental problem with multiple discount options that is also optimal. Some experimental results are also given to show the effectiveness of the algorithms when running on some real data and random data.
引文
[1]Karp R.On-Line algorithms versus off-line algorithms:How much is it worth to know the future-In:Proc.of the IFIP 12th World Computer Congress,Vol.1.1992.416-429.
[2]Karlin AR,Manasse MS,Rudolph L,Sleator DD.Competitive snoopy caching.Algorithmica,1988,3(1-4):79-119.[doi:10.1007/BF01762111]
[3]Lotker Z,Patt-Shamir B,Rawitz D.Rent,lease or buy:Randomized algorithms for multislope ski rental.In:Proc.of the STACS2008.New York:Springer-Verlag,2008.503-514.[doi:10.4230/LIPIcs.STACS.2008.1331]
[4]Fujiwara H,Kitano T,Fujito T.On the best possible competitive ratio for multislope ski rental.In:Proc.of the ISAAC 2011.LNCS 7074,Berlin,Heidelberg:Springer-Verlag,2011.544-553.[doi:10.1007/978-3-642-25591-5_56]1060 Journal of Software
[5]El-Yaniv R,Karp R.Nearly optimal competitive online replacement policies.Mathematics of Operations Research,1997,22(4):814-839.[doi:10.1287/moor.22.4.814]
[6]Augustine J,Irani S,Swamy C.Optimal power-down strategies.In:Proc.of the 45th IEEE Symp.on Foundations of Computer Science.Washington:IEEE Computer Society,2004.530-539.[doi:10.1109/FOCS.2004.50]
[7]Lotker Z,Patt-Shamir B,Rawitz D.Ski rental with two general options.Information Processing Letters,2008,108(6):365-368.[doi:10.1016/j.ipl.2008.07.009]
[8]Azar Y,Bartal Y,Feuerstein E,Fiat A,Leonardi S,Rosen A.On capital investment.Algorithmica,1999,25(1):22-36.[doi:10.1007/PL00009281]
[9]Dong YC,Xu YF,Xu WJ.Competitive analysis and risk-reward model for online rental problem with canceling buying-permission.Chinese Journal of Management Science,2007,18(4):28-33(in Chinese with English abstract).
[10]Zhang T.Online channel scheduling in wireless networks.Journal of Computer Research and Development,2008,45(S1):31-34(in Chinese with English abstract).
[11]Wang Y,Dong YC,Xu YF.Competitive analysis for the online multistage leasing problem.Chinese Journal of Management Science,2009,17(3):101-106(in Chinese with English abstract).
[12]Al-Binali S.A risk-reward framework for the competitive analysis of financial games.Algorithmica,1999,25(1):99-115.[doi:10.1007/PL00009285]
[13]Albers S,Charikar M,Mitzenmacher M.On delayed information and action in on-line algorithms.Information and Computation,2001,170(2):135-152.[doi:10.1006/inco.2001.3057]
[14]Fujiwara H,Iwama K.Average-Case competitive analyses for ski-rental problems.Algorithmica,2005,42(1):95-107.[doi:10.1007/s00453-004-1142-x]
[15]Xu Y,Xu W,Li H.On the on-line rent-or-buy problem in probabilistic environments.Journal of Global Optimization,2007,38(1):1-20.
[16]Irani S,Pruhs K.Algorithmic problems in power management.ACM SIGACT News,2005,36(2):63-76.[doi:10.1145/1067309.1067324]
[17]Zhang G,Poon CK,Xu Y.The ski-rental problem with multiple discount options.Information Processing Letters,2011,111(20):903-906.[doi:10.1016/j.ipl.2011.06.012]
[18]Meyerson A.The parking permit problem.In:Proc.of the 46th IEEE Symp.on Foundations of Computer Science.Washington:IEEE Computer Society,2005.274-284.[doi:10.1109/SFCS.2005.72]
[19]Zhang GQ,Xu YF,Wang Y.Competitive analysis for the online rental problem with multiple options.Operations Research and Management Science,2012,21(1):11-18(in Chinese with English abstract).
[20]Garey MR,Johnson DS.Computers and Intractability:A Guide to NP-Completeness.San Francisco:Freeman Co.,1979.
[9]董玉成,徐寅峰,徐维军.可退货在线租赁问题竞争分析及其风险回报模型.中国管理科学,2007,18(4):28-33.
[10]张韬.无线网络中的在线信道分配问题.计算机研究与发展,2008,45(增刊1):31-34.
[11]王扬,董玉成,徐寅峰.多阶段占线赁购问题竞争分析.中国管理科学,2009,17(3):101-106.
[19]张桂清,徐寅峰,王扬.在线多租赁选择问题的最优竞争策略.运筹与管理,2012 21(1):11-18.
[2]Karlin AR,Manasse MS,Rudolph L,Sleator DD.Competitive snoopy caching.Algorithmica,1988,3(1-4):79-119.[doi:10.1007/BF01762111]
[3]Lotker Z,Patt-Shamir B,Rawitz D.Rent,lease or buy:Randomized algorithms for multislope ski rental.In:Proc.of the STACS2008.New York:Springer-Verlag,2008.503-514.[doi:10.4230/LIPIcs.STACS.2008.1331]
[4]Fujiwara H,Kitano T,Fujito T.On the best possible competitive ratio for multislope ski rental.In:Proc.of the ISAAC 2011.LNCS 7074,Berlin,Heidelberg:Springer-Verlag,2011.544-553.[doi:10.1007/978-3-642-25591-5_56]1060 Journal of Software
[5]El-Yaniv R,Karp R.Nearly optimal competitive online replacement policies.Mathematics of Operations Research,1997,22(4):814-839.[doi:10.1287/moor.22.4.814]
[6]Augustine J,Irani S,Swamy C.Optimal power-down strategies.In:Proc.of the 45th IEEE Symp.on Foundations of Computer Science.Washington:IEEE Computer Society,2004.530-539.[doi:10.1109/FOCS.2004.50]
[7]Lotker Z,Patt-Shamir B,Rawitz D.Ski rental with two general options.Information Processing Letters,2008,108(6):365-368.[doi:10.1016/j.ipl.2008.07.009]
[8]Azar Y,Bartal Y,Feuerstein E,Fiat A,Leonardi S,Rosen A.On capital investment.Algorithmica,1999,25(1):22-36.[doi:10.1007/PL00009281]
[9]Dong YC,Xu YF,Xu WJ.Competitive analysis and risk-reward model for online rental problem with canceling buying-permission.Chinese Journal of Management Science,2007,18(4):28-33(in Chinese with English abstract).
[10]Zhang T.Online channel scheduling in wireless networks.Journal of Computer Research and Development,2008,45(S1):31-34(in Chinese with English abstract).
[11]Wang Y,Dong YC,Xu YF.Competitive analysis for the online multistage leasing problem.Chinese Journal of Management Science,2009,17(3):101-106(in Chinese with English abstract).
[12]Al-Binali S.A risk-reward framework for the competitive analysis of financial games.Algorithmica,1999,25(1):99-115.[doi:10.1007/PL00009285]
[13]Albers S,Charikar M,Mitzenmacher M.On delayed information and action in on-line algorithms.Information and Computation,2001,170(2):135-152.[doi:10.1006/inco.2001.3057]
[14]Fujiwara H,Iwama K.Average-Case competitive analyses for ski-rental problems.Algorithmica,2005,42(1):95-107.[doi:10.1007/s00453-004-1142-x]
[15]Xu Y,Xu W,Li H.On the on-line rent-or-buy problem in probabilistic environments.Journal of Global Optimization,2007,38(1):1-20.
[16]Irani S,Pruhs K.Algorithmic problems in power management.ACM SIGACT News,2005,36(2):63-76.[doi:10.1145/1067309.1067324]
[17]Zhang G,Poon CK,Xu Y.The ski-rental problem with multiple discount options.Information Processing Letters,2011,111(20):903-906.[doi:10.1016/j.ipl.2011.06.012]
[18]Meyerson A.The parking permit problem.In:Proc.of the 46th IEEE Symp.on Foundations of Computer Science.Washington:IEEE Computer Society,2005.274-284.[doi:10.1109/SFCS.2005.72]
[19]Zhang GQ,Xu YF,Wang Y.Competitive analysis for the online rental problem with multiple options.Operations Research and Management Science,2012,21(1):11-18(in Chinese with English abstract).
[20]Garey MR,Johnson DS.Computers and Intractability:A Guide to NP-Completeness.San Francisco:Freeman Co.,1979.
[9]董玉成,徐寅峰,徐维军.可退货在线租赁问题竞争分析及其风险回报模型.中国管理科学,2007,18(4):28-33.
[10]张韬.无线网络中的在线信道分配问题.计算机研究与发展,2008,45(增刊1):31-34.
[11]王扬,董玉成,徐寅峰.多阶段占线赁购问题竞争分析.中国管理科学,2009,17(3):101-106.
[19]张桂清,徐寅峰,王扬.在线多租赁选择问题的最优竞争策略.运筹与管理,2012 21(1):11-18.