Online algorithms improve performance using partial input samples
Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
Data Structures and Algorithms
Summary
This paper studies how online algorithms can use a small random sample of their input to do better than usual in problems like covering and facility location. The authors develop new algorithms that perform tightly within certain mathematical bounds, improving on previous work significantly. They also examine what happens if an adversary changes some sample points, giving robust algorithms that still perform well. Their results provide clear limits on how much help a sample can offer, even if partly corrupted.
What this means in practice
- •For network operators: Design online routing or resource allocation that adapts better using partial sampled traffic data, improving efficiency beyond worst-case guarantees.
- •For supply chain managers: Create dynamic facility location and coverage plans that maintain quality even when some sample data is unreliable or manipulated.
A theory result. No direct application yet.
Authors
Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor, Debmalya Panigrahi
Abstract
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 set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.