Competitive Analysis with a Sample and the Secretary Problem

By Haim Kaplan, David Naori, Danny Raz. 2019

51 citations recorded by the source corpus.

We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal both in the worst-cast and random-order models.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Game & Decision Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

In Algorithms & Complexity

Citations in the corpus

Secretary and Online Matching Problems with Machine Learned Advice (2020, background): “[19] consider a secretary problem with the assumption that the algorithm has access to a random sample of the adversarial distribution ahead of time.”
Secretaries with Advice (2020, methodology): “setting [16], its Markovian generalizations [2, 12, 18, 34], and the recently introduced sample-based variants [9, 21].”