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: <http://ie.technion.ac.il/seminar_files/1308462802_liri-finkelstein.html> 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 <techm@math.technion.ac.il> Announcement from: <dcarmel@.technion.ac.il>