带有多折扣选项的滑雪租赁问题的在线和离线算法?

摘要：

研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是 NP 难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.

关键词：在线算法、竞争比分析、滑雪租赁问题、带有多折扣选项的滑雪租赁问题

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金71150110492,61370071;中央高校基本科研业务费专项资金ZYGX2012J069

在线出版日期：2014-06-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1051-1060