This portal has been archived. Explore the next generation of this technology.
Improving Online Algorithms via ML Predictions
lib:f7688a8af4706bcb (v1.0.0)
Authors: Manish Purohit,Zoya Svitkina,Ravi Kumar
Where published: NeurIPS 2018 12
Document: PDF DOI
Abstract URL: http://papers.nips.cc/paper/8174-improving-online-algorithms-via-ml-predictions
In this work we study the problem of using machine-learned predictions to improve 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.
Where published: NeurIPS 2018 12
Document: PDF DOI
Abstract URL: http://papers.nips.cc/paper/8174-improving-online-algorithms-via-ml-predictions
In this work we study the problem of using machine-learned predictions to improve 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.
Relevant initiatives
Related knowledge about this paper
Reproduced results (crowd-benchmarking and competitions)
Artifact and reproducibility checklists
- ACM/cTuning artifact appendix and reproducibility checklist
- NeurIPS reproducibility checklist
- SIGPLAN's checklist for empirical evaluation
- Collective Knowledge (organizing research projects based on FAIR principles)