Competitive optimal on-line leasing

作     者：El-Yaniv, R Kaniel, R Linial, N 

作者机构：Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ Penn Wharton Business Sch Philadelphia PA 19104 USA Hebrew Univ Jerusalem Inst Comp Sci IL-91904 Jerusalem Israel 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：1999年第25卷第1期

页      面：116-140页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：leasing lease-or-buy problem on-line algorithms competitive analysis equipment rental ski rental 

摘      要：Consider an on-line player who needs same equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is determined whether the player will need the equipment during the current period and the player has two options: to pay a leasing fee c and rent the equipment for the period, or to buy it for a larger amount P. The total cost incurred by the player is the sum of all leasing fees and perhaps one purchase. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attention in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive performance is achieved by leasing for the first k - 1 times and then buying, where k = P/c. This strategy Days at most 2 - l/k times the optimal off-line cost. When considering alternative financial transactions one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper we determine both deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor reduces the uncertainty involved. We Rnd that the optimal deterministic competitive ratio is 1 + (1 + i)(l - l/k)(l - k(i/l + i)), a decreasing function of the interest i (for all reasonable values of i). For some applications, realistic values of interest rates result in relatively low competitive ratios. By using randomization the on-line player can further boost up the performance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller competitive