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

  • Ola Svensson | École Polytechnique Fédérale de Lausanne

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).

Speaker Details

Ola Svensson is an assistant professor in the theory group at EPFL. He is interested in fundamental questions in combinatorial optimisation related to the approximability of basic optimization problems. His work on the traveling salesman problem received the best paper award at FOCS’11.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks