betaFeedback

WorksComputer Science

Beyond Worst-Case Online Algorithms via Input Subsampling

Abstract

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>qp>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 22 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/pq/p. Against adversarial distributions over horizons, one unrestricted randomized algorithm achieves a strict simultaneous improvement over e/(e−1)e/(e-1) for every distribution exactly when q/pq/p is below approximately 0.340.34. Requiring the algorithm to buy by the breakeven time lowers this threshold to approximately 0.310.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.

Paper details

vlnc:W_ppuyxwbk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT 5.6Pro, Codex

View statement
Looking for related papers…