Thursday, March 17, 2016 4:00 pm
-
4:00 pm
EDT (GMT -04:00)
Title: The matroid secretary problem for minor-closed classes
Speaker: | Peter Nelson |
Affiliation: | University of Waterloo |
Room: | MC 5417 |
Abstract: In the secretary problem, we are instructed to hire secretary from a sequence of interviewees, where the qualities of the candidates is not known in advance, the order we interview is random, and the hiring decision must be made immediately after the interview. It is known to be possible to hire in such a way that the expected quality of the hired candidate is at least 1/e of the quality of the best candidate. We discuss an analogous problem where, instead of hiring a single secretary, we are required to hire a set of secretaries that is independent in a given matroid, considering the problem for minor-closed classes of representable matroids.