CS 269S, Winter 2012: Theory Seminar
Bren Hall, Room 1423
9 March 2012:

The Secretary Problem on Graphs

by Nitish Korula and Martin Pal presented in ICALP 2008

Presented by Ali Mehrabi

We begin the talk by defining the classical secretary problem and giving simple instance of the problem. Then we define a specific variant of the problem and present a constant ratio online randomized algorithm for it.