A multiple-choice secretary algorithm with applications to online auctions
Robert Kleinberg · 2005
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