A Knapsack Secretary Problem with Applications

By Moshe Babaioff, Nicole Immorlica, David Kempe, Robert D. Kleinberg. 2007

226 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Management Science and Operations Research, 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 Computational Theory and Mathematics

In Computer Networks and Communications

In Management Science and Operations Research

In Algorithms & Complexity

Citations in the corpus

Online Adversarial Attacks (2021, methodology): “Well-known single threshold-based algorithms that solve the k-secretary problem include the VIRTUAL, OPTIMISTIC Babaioff et al. (2007) and the recent SINGLE-REF algorithm Albers & Ladewig (2020). In a nutshell, these online algorithm consists of two phases—a sampling phase followed by a selection ph”
Truthful incentives in crowdsourcing tasks using regret minimization mechanisms (2013, background): “Recent research addresses various models of budget constraints including the online knapsack secretary problem [7] and the weighted secretary problem [5].”
A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, methodology): “However, this leads to very pessimistic performance bounds for this problem: no online algorithm can achieve better than O41/n5 approximation of the optimal offline solution (Babaioff et al. 2008). In contrast, although a priori input distribution can simplify the problem to a great extent, the choi”
Secretary Problems via Linear Programming (2010, methodology): “[4]) uses an algorithm that is 1/e competitive for maximizing the expected profit for small values of k (k ≤ 27).”
New Results for the $k$-Secretary Problem (2020, methodology): “[8].”
Submodular secretary problem and extensions (2010, unknown): “[4, 5, 6, 24, 28, 32]).”
Improved Online Algorithms for Knapsack and GAP in the Random Order Model (2020, methodology): “[7] was developed for the k-secretary problem and performs slightly better than single-ref in the case k = 2; the competitive ratios of both algorithms are 0.”