Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

Anish Hebbar, Ravi Kumar, Roie Levin +3

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…