Online Algorithms for Multi-shop Ski Rental with Machine Learned Predictions
Shufan Wang, Jian Li · 2020
Uncertainty plays a critical role in many real world applications where the decision maker is faced with multiple alternatives with different costs. These decisions arise in our daily lives, such as whether to rent an apartment or buy a house, which cannot be answered reliably without knowledge of the future. These decisionmaking problems are usually modeled as online rent-or-buy problems, such as the classical ski rental problem [4, 5, 8]. Two paradigms have been widely studied to deal with such uncertainty. On the one hand, online algorithms are designed without prior knowledge to the problem, and competitive ratio (CR) is used to characterize the goodness of the algorithm in lack of the future. On the other hand, machine learning is applied to address uncertainty by making future predictions via building robust models on prior data.