研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题...研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.展开更多
Many actual rental activities present online rental problems with multiple units of assets or equipment whose use can be continuous,separable,or discrete.Using online algorithms and competitive analysis,continuous mul...Many actual rental activities present online rental problems with multiple units of assets or equipment whose use can be continuous,separable,or discrete.Using online algorithms and competitive analysis,continuous multiple online rental problems have obtained the optimal risk control strategy and the optimal competitive ratio.For multiple online rental problems with discrete assets,first,we present an approximation algorithm for a risk control strategy and the upper bound of the optimal competitive ratio.Moreover,in practical applications,the approximation algorithm of the discrete online problem provides the approximate rental quantities in each period and the solution principle for the approximate competitive ratio.Second,we present the approximate optimal rental quantities and the correction algorithm to obtain a better competitive ratio based on the approximation algorithm.Finally,we compare the approximation algorithm with the correction algorithm by real data.Our findings show that when the approximate solution is used to replace the corrected solution,the resulting approximation error is usually less than the magnitude of 1/ms where m is the total units of certain assets or equipment and s is the price to buy one unit in each period.展开更多
文摘研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.
基金We would like to thank the anonymous referees and the senior/associate editors for their comments,which have significantly strengthened this paper.The authors would like to acknowledge the financial support of National Natural Science Foundation of China(71471065,71720107002)Guangdong Province Science and Technology Plan Project(2017A070706004)The Fundamental Research Funds for the Central Universities(2018YBXMPY09).
文摘Many actual rental activities present online rental problems with multiple units of assets or equipment whose use can be continuous,separable,or discrete.Using online algorithms and competitive analysis,continuous multiple online rental problems have obtained the optimal risk control strategy and the optimal competitive ratio.For multiple online rental problems with discrete assets,first,we present an approximation algorithm for a risk control strategy and the upper bound of the optimal competitive ratio.Moreover,in practical applications,the approximation algorithm of the discrete online problem provides the approximate rental quantities in each period and the solution principle for the approximate competitive ratio.Second,we present the approximate optimal rental quantities and the correction algorithm to obtain a better competitive ratio based on the approximation algorithm.Finally,we compare the approximation algorithm with the correction algorithm by real data.Our findings show that when the approximate solution is used to replace the corrected solution,the resulting approximation error is usually less than the magnitude of 1/ms where m is the total units of certain assets or equipment and s is the price to buy one unit in each period.
