带有多折扣选项的滑雪租赁问题的在线和离线算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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


Online and Offline Algorithms for the Ski-Rental Problem with Multiple Discount Options
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

肖鸣宇,沈正翔.带有多折扣选项的滑雪租赁问题的在线和离线算法.软件学报,2014,25(5):1051-1060

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2013-05-14
  • 最后修改日期:2013-09-02
  • 录用日期:
  • 在线发布日期: 2014-05-04
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号