2 - Ski-Rental

Summary

Introduction

In this chapter, we consider a canonical online problem that captures the basic decision question encountered in online algorithms. Assume that you arrive at a ski resort in the middle of the ski season. To rent a pair of skis, it takes $1 per day, while to buy them outright, it costs $P. On each new day, you only get to see whether the season is on-going or not, and have to decide whether to buy the ski or keep renting. The objective is to ski for as long as the season lasts with minimum cost possible without, however, knowing the remaining length of the skiing season. This problem is popularly known as the ski-rental problem. The ski-rental problem illustrates the inherent challenge of making decisions under uncertainty, where the uncertainty can even be controlled by an adversary depending on your current or past decisions.

The ski-rental problem models the classic rent/buy dilemma, where the uncertainty about future utility makes the problem challenging. It is highly relevant in various real-world applications, e.g., whether to rent/buy an expensive equipment or a luxury item with unknown number of days of utility, networking/scheduling problems where there are multiple servers with different service guarantees and prices. In scheduling, the following simple problem is equivalent to the ski-rental problem. Consider two servers, where one is shared and follows a FIFO discipline and has a minimal cost while the other is costly but dedicated. The decision to make for each user/packet is whether to stay with the shared server or jump to the dedicated one any time until it is served/processed.

In this chapter, we consider both deterministic and randomized algorithms for the ski-rental problem, and derive optimal algorithms in both settings, which is typically not possible for most of the other online problems considered in the book. We also describe the generic technique to lower bound the competitive ratio of randomized algorithms using Yao's principle. Two extensions of the ski-rental problem – the TCP (transmission control protocol) acknowledgement problem and the Bahncard problem – are also discussed at the end.