Skip to yearly menu bar Skip to main content


Advice Querying under Budget Constraint for Online Algorithms

Ziyad Benomar · Vianney Perchet

Great Hall & Hall B1+B2 (level 1) #1205
[ ]
[ Paper [ Slides [ OpenReview
Wed 13 Dec 8:45 a.m. PST — 10:45 a.m. PST


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.

Chat is not available.