Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Matroids, secretary problems, and online mechanisms

Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg


We study a generalization of the classical secretary problem which we call the "matroid secretary problem". In this problem, the elements of a matroid are presented to an online algorithm in random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision regarding whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. This paper presents an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.


Publication typeInproceedings
Published inSymposium on Discrete Algorithms (SODA'07)
> Publications > Matroids, secretary problems, and online mechanisms