Constant Competitive Online Algorithms for the Matroid Secretary Problem

Abstract: Matroids are a mathematical structure that generalize the linear independence in vector spaces and acyclic subgraphs in graphs, and have been applied in combinatorial optimization and discrete math. In the matroid secretary problem, a matroid M is given and an adversary assigns a weight to each element of M. The elements appear one by one in uniformly random order, and when an element e arrives, the weight w(e) is presented and an irrevocable decision to accept or reject element has to be made at that time. The goal of the problem is to design an online algorithm that selects an independent set whose weight is as large as possible. This problem generalizes the classical secretary problem and has applications in online auction and online mechanism design.

This problem was introduced by Babaioff, Immorlica and Kleinberg in 2007 and they gave an O(log(rank))-competitive online algorithm for the problem. They also conjectured that there is a constant-competitive online algorithm for it. This has been an active area of research for the past seven years with many incremental improvements. In this presentation, we show a constant competitive online algorithm for the matroid secretary problem in the MK (matroid-known) model, which resolves an open problem posed by Babaioff et al. This is joint work with Professor Hemanshu Kaul.

Event Topic

Discrete Applied Math Seminar