The Ski Rental Problem
Ski Rental Problem The ski rental problem is a classic example problem in online algorithms. It feels like a small but interesting problem that can be explained relatively easily while some clever tricks can be applied to it. In this article, I took these lecture notes by Debmalya Panigrahi and Hangjie Ji and tried to rewrite them in a way that is easier to understand (at least for me). Formulation You are going skiing in the mountains but you are unsure about the weather reports and don't k