Competitive Optimal On-Line Leasing

详细信息    查看全文

• 作者：R. El-Yaniv ; R. Kaniel and N. Linial
• 关键词：Key words. Leasing ; Lease ; or ; buy problem ; On ; line algorithms ; Competitive analysis ; Equipment rental ; Ski rental.
• 刊名：Algorithmica
• 出版年：1999
• 出版时间：May 1999
• 年：1999
• 卷：25
• 期：1
• 页码：116-140
• 全文大小：205 KB

文摘

Consider an on-line player who needs some 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.