论文标题
在线算法多购物中心滑雪租赁的租赁
Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
论文作者
论文摘要
我们研究了使用机器学习（ML）建议增强在线算法的问题。特别是，我们考虑\ emph {Multi-Shop Ski Rental}（MSSR）问题，这是对经典滑雪租赁问题的概括。在MSSR中，每家商店的购买和租用滑雪板的价格都不同，滑雪者必须决定何时和何时购买。当使用单个或多个ML预测做出决策时，我们获得具有确定性的和随机的在线算法，并且可证明性能得到改善。这些在线算法对ML预测的质量或预测错误类型不了解。这些在线算法的性能对预测因子的性能不佳，但通过更好的预测提高。使用合成和现实世界数据的广泛实验验证了我们的理论观察，并针对纯粹依赖在线决策的算法显示出更好的性能。
We study the problem of augmenting online algorithms with machine learned (ML) advice. In particular, we consider the \emph{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 prediction. The performance of these online algorithms are robust to the poor performance of the predictors, but improve with better predictions. Extensive experiments using both synthetic and real world data traces verify our theoretical observations and show better performance against algorithms that purely rely on online decision making.
