Knapsack Secretary is not $1/e$-Competitive
2026-07-27 • Data Structures and Algorithms
Data Structures and AlgorithmsComputer Science and Game Theory
AI summaryⓘ
The authors prove that no algorithm can reach the previously believed best performance of 1/e (about 0.3679) for the knapsack secretary problem, specifically showing a stricter limit of about 0.36437 in a special case. This problem involves choosing items in random order to maximize value without exceeding capacity. They build on earlier results and answer an open question by showing the limit holds even when full numerical values are known, not just relative ranks. Additionally, they provide a new algorithm that performs better than existing ones for certain cases with multiple knapsacks.
knapsack secretary problemcompetitive ratioalgorithmic impossibilityrandom-order algorithmscardinal vs ordinal informationonline algorithmssecretary problemknapsack constraints
Authors
Marius Garbea, Rishi Patel, Emmanouil Pountourakis
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 \geq 2$. This improves the guarantee obtained by applying general-purpose random-order knapsack algorithms to this special case.