Technion, IEM faculty - Information Systems seminar
Speaker: Liri Finkelstein
Title: Circuits Algorithm for the Matroid Secretary Problem
Date: 28/06/2011
Time: 13:00
Place: Bloomfield-527
Abstract:  <>
Or read this:
The matroid secretary problem is a setting in which elements arrive at a 
random order, and the algorithm must make an irrevocable decision 
whether or not to select this element. Not all subsets of elements can 
be selected, only those subsets that are independent sets of a 
pre-specified matroid. Each element has a weight, that is revealed when 
the element arrives, and the goal is to select a subset of elements with 
maximal weight. The offline problem is optimally solved by a greedy 
algorithm for any matroid. An open question is whether constant 
competitiveness is achievable for all matroids. Several attempts to 
answer this question during the last decade yielded solutions for some 
important classes of matroids: uniform, partition, transversal, graphic, 
and laminar.
I define a new algorithm, the circuits algorithm, and show that it has 
constant competitive ratios for several special cases of matroids that 
were not studied before. An interesting property of algorithm is that it 
uses only terms of general matroids, and does not rely on the specific 
structure of the matroid. 
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>