Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Matroid Secretary for Regular and Decomposable Matroids
event speaker icon
Michael Dinitz (Weizmann Institute of Science)
event date icon
Wednesday, 05.06.2013, 12:30
event location icon
Taub 201
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.