Preprint
Sep 2026
Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for...
A. Hebbar, Ravi Kumar, Roie Levin et al.
· 0 citations