The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is e/(e−1)-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of competitive ratio exceeding 2, and a Θ(1/n) chance of the competitive ratio exceeding n.
We ask what happens to the optimal solution if we insist that the tail risk, i.e., the chance of the competitive ratio exceeding a specific value, is bounded by some constant δ. We find that this additional modification significantly changes the structure of the optimal solution. The probability of purchasing skis on a given day becomes non-monotone, discontinuous, and grows arbitrarily quickly (for sufficiently small tail risk δ and large purchase cost n).
Joint work with Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii
Michael Dinitz is an Associate Professor in the Department of Computer Science at Johns Hopkins University, with a secondary appointment in the Department of Applied Mathematics and Statistics. He was previously a postdoctoral fellow at the Weizmann Institute of Science, and received his PhD from Carnegie Mellon University. He works primarily in theoretical computer science, with a focus on approximation and graph algorithms, and occasionally with applications to computer networking, distributed computing, or machine learning.