The Power of a Random Sample in Online Algorithms

In this paper, we introduce a semi-random model in online optimization, which interpolates naturally between the standard (adversarial) and random-order arrival model, which we call the online with a random sample (ORS) model: the full input may be chosen adversarially, but a random $p$-fraction of the input is selected and presented to the algorithm in random-order, before the remaining non-sampled elements are presented (in adversarial order). While similar in spirit to the AOS (adversarial order with a sample) model introduced by Kaplan, Naori and Raz, in our ORS model, the sampled $p$-fraction is revealed online instead of offline, and hence, competitiveness is measured with respect to the full input. Our central focus in the paper is applying the ORS model to the secretary problem and its natural $(k,1)$ variant. For the secretary problem, we present an optimal $pe^{-p}$-competitive algorithm, while for the $(k,1)$-secretary problem, we obtain a competitive algorithm whose performance converges to optimal competitiveness as $p\rightarrow 1$. We also include a $O(\log (1/p))$-competitive algorithm for facility location.