December 26th, Wednesday 14:15, Room 303, Jacobs Building

Title: The Matroid Secretary Problem

Lecturer: Oded Lachish

Lecturer homepage : http://www.dcs.bbk.ac.uk/~oded/

Affiliation : University of London

 

The Matroid Secretary Problem, formalized 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 log the matroid's rank. Until 2012 this result has been the state of the art. It is conjectured that a constant competitive ratio is achievable for this problem. Here will discuss the background and state of the art results for this problem. Extra attention will be given to a result by Chakraborty and Lachish which achieves a competitive ratio of square root log the matroid's rank.