Competitive Algorithms for an Online Rent or Buy Problem with Variable Demand
Rohan Kodialam · SIAM Undergraduate Research Online · 2014
We consider a generalization of the classical Ski Rental Problem motivated by applications in cloud computing.We develop deterministic and probabilistic online algorithms for rent/buy decision problems with time-varying demand.We show that these algorithms have competitive ratios of 2 and 1.582 respectively.We also further establish the optimality of these algorithms.