Can I read Secretary Problems with Non-Uniform Arrival Order on EtoBox?

Secretary Problems with Non-Uniform Arrival Order by Thomas Kesselheim; Robert Kleinberg; Rad Niazadeh is a scholarly article available to read on EtoBox.

What is Secretary Problems with Non-Uniform Arrival Order about?

For a number of problems in the theory of online algorithms, it is known that the assumption that elements arrive in uniformly random order enables the design of algorithms with much better performance guarantees than under worstcase assumptions. The quintessential example of this phenomenon is the secretary problem, in which an algorithm attempts to stop a sequence at the moment it observes the maximum value in the sequence. 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 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. Toward this end, we present two sets of properties of distributions over permutations as sufficient conditions,

Author

Thomas Kesselheim; Robert Kleinberg; Rad Niazadeh

Publisher

ACM

Published

2015

Language

EN