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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 14,2013
  • Revised:September 02,2013
  • Adopted:
  • Online: May 04,2014
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063