Tim Oosterwijk  (UM) 

The secretary problem with independent sampling

Sequential decision making under uncertainty is a basic problem that bridges several areas. Examples include online algorithms in computer science, and optimal stopping problems with stochastic input in the field of operations research and applied probability.

In this talk, I will discuss the secretary problem, where we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value.

We aim to quantify the relation between having more a priori information at our disposal regarding the online values and the success probability we can obtain. We do this by sampling each element independently with a fixed probability p before starting the online sequence. For both the adversarial order case and the random order case, we obtain best possible algorithms for every value of p.

VIDEOSTREAM