Improved algorithms and analysis for secretary problems and generalizations

Abstract

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k = 1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known; even the question of whether or not the expected sum of powers of the ranks of selected items tends to infinity with n has been unresolved. We answer these open questions by obtaining explicit algorithms. For each z ≥ 1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most 1 k z+1/(z + 1) + C(z) · k z+0.5 log k, whereas the best possible value at all is k z+1/(z + 1) + O(k z). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and its expected rank.