Online Algorithms for Multi-shop Ski Rental with Machine Learned Predictions
share
We study the problem of augmenting online algorithms with machine learned (ML) predictions. In particular, we consider the multi-shop ski rental (MSSR) problem, which is a generalization of the classical ski rental problem. In MSSR, each shop has different prices for buying and renting a pair of skis, and a skier has to make decisions on when and where to buy. We obtain both deterministic and randomized online algorithms with provably improved performance when either a single or multiple ML predictions are used to make decisions. These online algorithms have no knowledge about the quality or the prediction error type of the ML predictions. The performance of these online algorithms are robust to the poor performance of the predictors, but improve with better predictions. We numerically evaluate the performance of our proposed online algorithms in practice.
READ FULL TEXT