Preprint
Knapsack Secretary is not1/e -Competitive
27 Jul 2026
Abstract
We prove that no algorithm for the knapsack secretary problem can be1/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 the1/eimpossibility barrier has remained unchanged. Many combinatorial variants of the secretary problem, including knapsack secretary, inherit the1/eimpossibility by embedding the single-choice problem as a special case. We construct a family of hard instances for the1 - Bknapsack 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 most0.36437 < (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 of1/(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 that1/ecannot be achieved even in the cardinal case of the1 - Bknapsack secretary problem. We complement our impossibility result with a simple algorithm for1 - Bknapsack secretary that is(1/5.10-o(1)) -competitive for every fixedB ≥ 2 . This improves the guarantee obtained by applying general-purpose random-order knapsack algorithms to this special case.
Metrics
1 Record Views
Details
- Title
- Knapsack Secretary is not1/e -Competitive
- Creators
- Marius Garbea - Drexel UniversityRishi Patel - Drexel UniversityEmmanouil Pountourakis - Drexel University
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science
- Other Identifier
- 991022198755804721