Skip to content Search
Search our website:

Matroid-Secretary-Problem

  • Speaker: Oded Lachish, Department of Computer Science and Information Systems, Birkbeck, University of London
  • Date: Wednesday, 16 February 2011 from 16:45
  • Location: Room 745, Malet Street building

Imagine that you want to hire a single secretary. For this goal you interview fifty candidates. Ideally you would like to decide whom to hire after the interviews. However due to managerial constraints, after each interview you must make an irrevocable decision whether to hire or not. How can the probability of hiring an optimal candidate be maximized?

The scenario just described is an illustration of the classical-secretary-problem, which was introduced in the sixties. Although the problem has long been solved, many of its generalizations are still open and receive significant attention. We will discuss on-going research regarding a specific generalization called the Matroid-Secretary-Problem.There the candidates are elements of a Matroid. Like in the classical case the decision whether to hire is irrevocable. Yet unlike the classical problem it is possible to hire more than one candidate, as long as all the hired candidates form an independent set. The goal is to maximize the expected value of the candidates hired.