Abstract
A famous conjecture by Babaioff, Immorlica, and Kleinberg states that there is a constant competitive algorithm for the Matroid Secretary Problem. Our current best algorithms are however quite far from proving this conjecture: they have a O(loglog rank)-competitive ratio, where rank equals the largest cardinality of a feasible set. In this talk, I give an overview of recent progress on this problem. Apart from the Matroid Secretary Problem, we will also see how this progress led to the development of better algorithms for other online selection problems, such as Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. Finally, I hope to stimulate further research by pointing out several related open problems. In particular, we have a candidate approach for the Matroid Secretary Problem that we so far are unable to analyze.