Improving Online Algorithms via ML Predictions
About
In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.
Ravi Kumar, Manish Purohit, Zoya Svitkina• 2024
Related benchmarks
| Task | Dataset | Result | Rank | |
|---|---|---|---|---|
| Online Decision Making | 10,000 trials drawn from Unif[1, 500], N(100, 30^2), and Exp(0.01) priors | Mean CR1.156 | 4 | |
| Ski Rental Problem | unif100 | Consistency1.1866 | 3 | |
| Ski Rental Problem | unif200 Uniform on {1, ..., 200} | Consistency1.3643 | 3 | |
| Ski Rental Problem | gauss Discretized truncated Gaussian N(50, 12^2) | Consistency1.4195 | 3 | |
| Ski Rental Problem | geom Truncated geometric with parameter 0.05 | Consistency1.4183 | 3 | |
| Ski Rental Problem | twopoint distribution 0.7δ30 + 0.3δ120 | Consistency1.2547 | 3 |
Showing 6 of 6 rows