Everybody is welcome to this public talk.

Title: Generalized Matroid Secretary Problem

Abstract:The classical secretary problem is the following:

there are $n$ candidates for a secretarial post. Only one of them has to be selected for the post. All the candidates are interviewed sequentially in a random order. After each interview a score is given to the candidate just interviewed. The goal is to select the candidate with a maximum score. But there is a catch. As soon as a candidate is interviewed, the decision whether to hire or not, has to be taken before the next candidate arrives. If that candidate is hired then the interview process stops. If the candidate is not hired then the next candidate is interviewed, and the candidate that was not hired cannot be hired in the future. Because of this catch, the best that can be done, is to maximize the probability of picking the best candidate. The Matroid Secretary Problem, introduced by Babaioff et al. (2007), is a generalization of the Classical Secretary Problem. In this problem, elements from a matroid are presented to an on-line algorithm in a random order. Each element has a weight associated with it, which is revealed to the algorithm along with the element. After each element is revealed the algorithm must make an irrevocable decision on whether or not to select it. The goal is to pick an independent set with the sum of the weights of the selected elements as large as possible. Babaioff et al. gave an algorithm for the Matroid Secretary Problem with a competitive ratio of O(log d), where d is the rank of the matroid It has been conjectured that a constant competitive ratio is achievable for this problem. We give an algorithm that has a competitive ratio of O(\sqrt{log d}). This is based on a joint work with Oded Lachish.