Advice Querying Under Budget Constraint for Online Algorithms
Abstract
Several problems have been extensively studied in the learning-augmented setting, where the algorithm has access to some, possibly incorrect, predictions. However, it is assumed in most works that the predictions are provided to the algorithm as input, with no constraint on their size. In this paper, we consider algorithms with access to a limited number of predictions, that they can request at any time during their execution. We study three classical problems in competitive analysis, the ski rental problem, the secretary problem, and the non-clairvoyant job scheduling. We address the question of when to query predictions and how to use them.
Cite
Text
Benomar and Perchet. "Advice Querying Under Budget Constraint for Online Algorithms." Neural Information Processing Systems, 2023.Markdown
[Benomar and Perchet. "Advice Querying Under Budget Constraint for Online Algorithms." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/benomar2023neurips-advice/)BibTeX
@inproceedings{benomar2023neurips-advice,
title = {{Advice Querying Under Budget Constraint for Online Algorithms}},
author = {Benomar, Ziyad and Perchet, Vianney},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/benomar2023neurips-advice/}
}