2 papers
cs.DS2026
Knapsack Secretary is not -Competitive
Marius Garbea, Rishi Patel, Emmanouil Pountourakis
We prove that no algorithm for the knapsack secretary problem can be -competitive. The knapsack secretary problem was first introduced by Babaioff, Immorlica, Kempe, and Klein…
cs.GT2025
Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
Robin Bowers, Marius Garbea, Emmanouil Pountourakis +1
This paper derives polynomial-time approximation schemes for several NP-hard stochastic optimization problems from the algorithmic mechanism design and operations research literatu…