Answers are grounded in this paper and cite their sources.
In the classical secretary problem, a set S of numbers is presented to an online algorithm in random order. At any time the algorithm may stop and choose the current element, and the goal is to maximize the probability of choosing the largest element in the set. We study a variation in which the algorithm is allowed to choose k elements, and the goal is to maximize their sum. We present an algorithm whose competitive ratio is 1- O(~/~). To our knowledge, this is the first algorithm whose competitive ratio approaches 1 as k-- ~ cx~. As an application we solve an open problem in the theory of online auction mechanisms. 1
No takes yet. Share an insight, caveat, or question.
Robert Kleinberg (2005) studied this question.