Matroid Theory Seminar - Peter Nelson

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.