Knapsack Secretary is not $1/e$-Competitive

Abstract

We prove that no algorithm for the knapsack secretary problem can be $1/e$-competitive. The knapsack secretary problem was first introduced by Babaioff, Immorlica, Kempe, and Kleinberg (2007). There have been many improvements to the achievable competitive ratio since then, but the $1/e$ impossibility barrier has remained unchanged. Many combinatorial variants of the secretary problem, including knapsack secretary, inherit the $1/e$ impossibility by embedding the single-choice problem as a special case. We construct a family of hard instances for the $1$-$B$ knapsack secretary problem, which is a special case of the general knapsack secretary problem, to improve the existing impossibility result. We show in this special case that the competitive ratio is at most $0.36437<\frac{1}{e}-0.0035$. Our construction is similar to the one used by Abels, Ladewig, Schewior, and Stinzendörfer (2022), for which they show an impossibility of $1/(1+e)$ for ordinal algorithms, where only the relative ranks of the items are known. Our work resolves an open question of theirs by showing that $1/e$ cannot be achieved even in the cardinal case of the $1$-$B$ knapsack secretary problem. We complement our impossibility result with a simple algorithm for $1$-$B$ knapsack secretary that is $(1/5.10-o(1))$-competitive for every fixed $B\ge 2$. This improves the guarantee obtained by applying general-purpose random-order knapsack algorithms to this special case.

34 pages, 1 figure