Robert Kleinberg: Secretary Problems with Non-Uniform Arrival Order

ABSTRACT:
For a number of problems in the theory of online algorithms, the assumption that elements arrive in uniformly random order enables the design of algorithms with much better performance guarantees than under worst-case assumptions. The quientessential example of this phenomenon is the secretary problem, in which an algorithm attempts to stop a sequence at the moment it observes the element of maximum value. As is well known, if the sequence is presented in uniformly random order there is an algorithm that succeeds with probability 1/e, whereas no non-trivial performance guarantee is possible if the elements arrive in worst-case order.

In many 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, by focusing on the secretary problem and asking what performance guarantees one can prove under relaxed assumptions. Along the way to answering this question we will encounter some tools, such as coding theory and approximation theory, not normally associated with the analysis of online algorithms.

Joint work with Thomas Kesselheim and Rad Niazadeh.

BIO:
Robert Kleinberg is an Associate Professor of Computer Science at Cornell University, currently visiting Microsoft Research New England. His research studies the design and analysis of algorithms, and their applications to electronic commerce, networking, information retrieval, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies, where he assisted in designing the world's largest Internet Content Delivery Network. He is the recipient of a Microsoft Research New  Faculty Fellowship, an Alfred P. Sloan Foundation Fellowship, and an NSF CAREER Award.