A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem

Опубликовано 22 июня 2016, 0:21

The last decade has seen an increased interest in generalizations of the secretary problem, a classical online selection problem. These generalizations have numerous applications in mechanism design for settings involving the selling of a good (e.g. ads) to agents (e.g. page views) arriving online. The matroid secretary problem is one of the most well-studied variants. It is general enough to deal with complex settings and, at the same time, it is sufficiently restricted to admit strong algorithms. A famous conjecture states that there is in fact a O(1)-competitive algorithm for the matroid secretary problem. This is an online algorithm that, in expectation and up to a constant factor, performs as well as any offline algorithm with perfect information. In this talk, we present a new method that improves on the previously best algorithm, in terms of simplicity and its competitive ratio. The main idea of our algorithm is to decompose the problem into a distribution over a simple type of matroid secretary problems which are easy to solve. We show that this leads to a O(loglog(rank))-competitive procedure. This is joint work with Moran Feldman (EPFL) and Rico Zenklusen (ETHZ).