A multiple-choice secretary algorithm with applications to online auctions

By Robert D. Kleinberg. 2005

315 citations recorded by the source corpus.

Subfields: Game & Decision Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Game & Decision Theory

In Algorithms & Complexity

Citations in the corpus

A Knapsack Secretary Problem with Applications (2007, methodology): “We show how to apply an intuitive algorithmic idea proposed by Babaioff et al. [2] to get a e-competitive algorithm for this problem for any k. Hence, our result improves upon the competitive ratio of the algorithm by Kleinberg [ 11 ] for small k and is significantly simpler.”
Secretary Problems via Linear Programming (2010, background): “For example, Kleinberg [20] studied a setting in which the algorithm is allowed to select multiple candidates and the goal is to maximize the expected profit.”
The adwords problem: online keyword matching with budgeted bidders under random permutations (2009, background): “Random permutation models have also been considered in other problems, perhaps most popular in the classic secretary problem and its generalizations [6, 2, 14].”
Prophet Secretary (2015, background): “For example, whenf(T) is the maximum individual value [13, 14], or when f(T) is the sum of the individual values in T [20], the problem has been considered thoroughly in the lite rature.”
A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, background): “This probability calculation is similar to the one used by Kleinberg (2005) in his proof of the necessity of condition B3⁄4ì41/25.”
Robust Algorithms for the Secretary Problem (2019, methodology): “algorithm for Byzantine secretary on uniform matroids of 3 rank K poly„ε1 logn”that is „1 +ε”-competitive with the benchmarkV. For the standard version of the problem, i.e. without any red elements, [Kle05] gave an algorithm that achieves the same competitiveness whenK Ω„1šε2”. „e algorithm from [Kl”
Improved Online Algorithms for Knapsack and GAP in the Random Order Model (2020, methodology): “l-known example is the secretary problem [16,32]. Nowadays, the matroid secretary problem [8,19] is considered as one of the most central problems in this eld. Further multiple-choice generalizations [13,30] are part of active research as well. The model has also been successfully applied to other p”
New Results for the $k$-Secretary Problem (2020, methodology): “The large interest in generalizations of the classical secretary problem is motivated mainly by numerous applications in online market design [10,16, 17].”
Competitive Analysis with a Sample and the Secretary Problem (2019, unknown): “oofs in this paper suggests. 3 1.1 Further RelatedWork Since the secretary problem was solved by Lindley [14] and Dynkin [7], various online problems have been studied in the random-order model (e.g. [2, 3, 12, 13]), many of which are motivated by the relation to online mechanism design. Kesselheim ”
Prophet Inequalities with Limited Information (2013, background): “We remark that there exist competitive algorithms for the secretary problem when J is a uniform matroid [17], a laminar matroid [16], graphic matroid [19], a transversal matroid [12], or a bipartite matching [19].”
Survey of Fog Computing: Fundamental, Network Applications, and Research Challenges (2018, methodology): “Based on the online k-secretary framework [147], in exploration stage, a fog node decides how to offload the computation tasks between other fog nodes and the cloud server.”