In the matroid secretary problem we are given a stream of elements in random order 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 [Proceedings of SODA'07] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g., graphic, cographic, and transversal matroids). In particular, there is very little known about $F$-representable matroids (the class of matroids that can be represented as elements of a vector space ove...
['Michael Dinitz', 'Guy Kortsarz']
Matroid Secretary for Regular and Decomposable Matroids