Improved algorithms and analysis for secretary problems and generalizations

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 a bout 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 expectatio n 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 choic es. Optimal algorithms for the special case of k = 1 are well known. Partial so lutions for the rst variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known. It seems that the fact that the expected sum of powers of the ranks of sel ected items is bounded as n tends to infinity has been known to follow from standard results. We derive our results by obtaining explicit algorithms. For each z greater than or equal to 1, the resulting expected sum of the zt h powers of the ranks of the selected objects is at most k(z+1)/(z + 1) + C (z) . k(z+0.5) log k, where log k = max {1, log(2) k}, whereas the best pos sible value at all is k(z+1)/(z + 1) + O(k(z)). Our methods are very intuit ive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and the expe cted rank of the selected object.