Secretary Problems with Non-Uniform Arrival Order

For many online problems, it is known that the uniform arrival order enables the design of algorithms with much better performance guarantees than under worst-case. The quintessential example is the secretary problem. If the sequence of elements is presented in uniformly random order there is an algorithm that picks the maximum value with probability 1/e, whereas no non-trivial performance guarantee is possible if the elements arrive in worst-case order. This work initiates an investigation into relaxations of the random-ordering hypothesis in online algorithms, by focusing on the secretary problems. We present two sets of properties of distributions over permutations as sufficient conditions, called the block-independence property and uniform-induced-ordering property. We show these two are asymptotically equivalent by borrowing some techniques from the approximation theory. Moreover, we show they both imply the existence of secretary algorithms with constant probability of correct selection, approaching the optimal constant 1/e in the limit. We substantiate our idea by providing several constructions of distributions that satisfy block-independence. We also show that Θ(log log n) is the minimum entropy of any permutation distribution that permits constant probability of correct selection in the secretary problem with n elements. While our block-independence condition is sufficient for constant probability of correct selection, it is not necessary; however, we present complexity-theoretic evidence that no simple necessary and sufficient criterion exists. Finally, we explore the extent to which the performance guarantees of other algorithms are preserved when one relaxes the uniform random ordering assumption, obtaining a positive result for Kleinberg's multiple-choice secretary algorithm and a negative result for the weighted bipartite matching algorithm of Korula and Pal.