Title: A O(log log (rank) ) - competitive algorithm for the matroid secretary problem
| Speaker: | David Aleman |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: In the Matroid Secretary problem the weighted elements of a matroid arrive one by one in a uniformly random order where an online algorithm observes the value of the element and must make an irrevocable decision of whether or not to include the element in its solution before the arrival of the next element. The goal is to maximize the total value of the chosen elements under the condition that they must constitute an independent set. Other than knowing the cardinality of the ground set and having access to an independence oracle, the algorithm has no further information about the matroid.
We say that an algorithm is c-competitive if the expected weight of the independent set returned by the algorithm is at least OPT/c, where OPT denotes the weight of the offline optimum.
The Secretary Problem Conjecture, stated by Babaioff, Immorlica and Kleinberg, states in its weak form that there exists an algorithm for the matroid secretary problem with a constant competitive ratio, and in its stronger form it states that this competitive ratio is e, matching the optimal competitiveness of the classical secretary problem. Despite numerous attempts by the CS community, the conjecture remains unsolved.
In this talk we review a O(log log(rank) ) - competitive algorithm due to Feldman, Svensson and Zenlkusen, where rank denotes the rank of the given matroid.