The Taub Faculty of Computer Science Events and Talks

In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream then we can never get rid of it, and if we choose not to accept it then we cannot later add it. Babaioff, Immorlica, and Kleinberg [SODA 2007] introduced this problem and conjectured that every matroid admits an O(1)-competitive algorithm. While many classes of matroids are known to admit O(1)-competitive algorithms (e.g. graphic, laminar, and transversal matroids), a fundamental class of matroids is still open: vector matroids. We take a first step in this direction by giving an O(1)-competitive algorithms for regular matroids, the class of matroids that are representable as vector spaces over any field. Moreover, unlike much previous work our techniques are fundamentally matroid-theoretic rather than graph-theoretic.

Joint work with Guy Kortsarz.