Knapsack Secretary is not $1/e$-Competitive

Marius Garbea, Rishi Patel, Emmanouil Pountourakis

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 Klein…