Uncertainty Whiteboard Seminar

Secretary Problems with Non-Uniform Arrival Order

The secretary problem is a quintessential example of an online problem, in which the assumption that elements arrive in uniformly random order enables the design of algorithms with much better performance guarantees than under worst-case assumptions.

In many of the applications of online algorithms, it is reasonable to assume there is some randomness in the input sequence, but unreasonable to assume that the arrival ordering is uniformly random. This work initiates an investigation into relaxations of the random-ordering hypothesis in online algorithms, by focusing on the secretary problem and asking what performance guarantees one can prove under relaxed assumptions.

Joint work with Bobby Kleinberg and Rad Niazadeh