Improving Online Algorithms via ML Predictions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911966527750144 |
|---|---|
| author | Kumar, Ravi Purohit, Manish Svitkina, Zoya |
| author_facet | Kumar, Ravi Purohit, Manish Svitkina, Zoya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17712 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improving Online Algorithms via ML Predictions Kumar, Ravi Purohit, Manish Svitkina, Zoya Data Structures and Algorithms Machine Learning 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. |
| title | Improving Online Algorithms via ML Predictions |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2407.17712 |