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.