Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
The robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify elements of the p-sample, is introduced and the first results for robust algorithms in the OAS setting are presented.