25 Jul 2024 | Ravi Kumar, Manish Purohit, Zoya Svitkina
This paper explores the use of machine-learned predictions to enhance the performance of online algorithms. The authors focus on two classical problems: ski rental and non-clairvoyant job scheduling. For the ski rental problem, where the number of skiing days is unknown, they propose a deterministic algorithm that is $(1 + 1/\lambda)$-robust and $(1 + \lambda)$-consistent, and a randomized algorithm that is $(\frac{1 + 1/b}{1 + e^{-(1 + 1/b)}})$-robust and $(\frac{\lambda}{1 + e^{-\lambda}})$-consistent. For the non-clairvoyant job scheduling problem, they introduce a randomized algorithm that is $(2/(1 - \lambda))$-robust and $(1/\lambda)$-consistent. The main contributions include provable guarantees on the performance of these algorithms, even when the predictions are not perfect. The paper also discusses the trade-offs between robustness and consistency, and provides experimental results showing that the proposed algorithms outperform classical methods, even with significant prediction errors.This paper explores the use of machine-learned predictions to enhance the performance of online algorithms. The authors focus on two classical problems: ski rental and non-clairvoyant job scheduling. For the ski rental problem, where the number of skiing days is unknown, they propose a deterministic algorithm that is $(1 + 1/\lambda)$-robust and $(1 + \lambda)$-consistent, and a randomized algorithm that is $(\frac{1 + 1/b}{1 + e^{-(1 + 1/b)}})$-robust and $(\frac{\lambda}{1 + e^{-\lambda}})$-consistent. For the non-clairvoyant job scheduling problem, they introduce a randomized algorithm that is $(2/(1 - \lambda))$-robust and $(1/\lambda)$-consistent. The main contributions include provable guarantees on the performance of these algorithms, even when the predictions are not perfect. The paper also discusses the trade-offs between robustness and consistency, and provides experimental results showing that the proposed algorithms outperform classical methods, even with significant prediction errors.