arXiv:2611.15711 · v1

Beyond Worst-Case Online Algorithms via Input Subsampling

首次提交 2026-11-12 00:53

版本更新 2026-11-12 00:53

雷达观测 2026-11-13 14:16

摘要

We study whether classical competitive ratios survive input subsampling, when both the online algorithm and the offline optimum are evaluated on the same subsampled input. We consider the canonical problems of prophet inequalities and ski-rental. In these settings, for any single subsampling rate, the classical worst-case ratios remain unchanged. We ask a stronger question: can one adversarial input remain worst-case at two distinct rates $p>q$? For prophet inequalities, in the model where the policy knows the sampling rate and learns item survival online, every instance has competitive ratio strictly below $2$ at one of the two rates, and we determine the tight simultaneous guarantee. For ski rental, in the fluid model where sampling scales the horizon, the answer depends on $q/p$. Against adversarial distributions over horizons, one unrestricted randomized algorithm achieves a strict simultaneous improvement over $e/(e-1)$ for every distribution exactly when $q/p$ is below approximately $0.34$. Requiring the algorithm to buy by the breakeven time lowers this threshold to approximately $0.31$, showing that unlike classical ski-rental algorithms, buying later can provably help in this setting. Our results therefore reveal a new form of beyond-worst-case fragility under input subsampling: instances that are worst-case at one rate need not remain hard at two rates simultaneously.

作者备注：Accepted to ITCS 2027