Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

Zvi Lotker, Boaz Patt-Shamir & Dror Rawitz
In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an...