← All papers
First page of Beyond Worst-Case Online Algorithms via Input Subsampling

Beyond Worst-Case Online Algorithms via Input Subsampling

Siddhartha Banerjee, Tianle Jiang, Kamesh Munagala

cs.DS Nov 11, 2026 · v1 cs.GT
Analytic lemmas about the ski-rental dual-weight function U are machine-checked in Lean, partly AI-generated, with a public GitHub repository.
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.

The paper asks whether worst-case instances for online problems (prophet inequalities, ski rental) remain worst-case when the same input is independently subsampled at two distinct rates p>q.

For prophet inequalities, a dynamic-programming analysis in a revealed-rate model gives a tight simultaneous competitive-ratio bound. For ski rental in a fluid model, a residual-curve and duality analysis couples horizons y and ρy. Certain analytic properties of the dual-weight function U_{ρ,ξ}(t) are verified in Lean, with a power-series representation taken as an axiom. The Lean proofs were partly produced with GPT assistance.

For prophet inequalities, every instance has ratio strictly below 2 at one of the two rates, and the tight simultaneous guarantee is determined. For distributional ski rental, a strict improvement over e/(e-1) is possible exactly when q/p is below about 0.34, or about 0.31 if the algorithm must buy by the breakeven time.