Establishes Ω((log T)^2) lower bound on regret for multi-secretary problem with gapped distributions via Bellman certificates, showing prior O((log T)^2) upper bounds are tight.
Operations Research 73(3):1273--1288
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
Establishes Ω((log T)^2) lower bound on regret for multi-secretary problem with gapped distributions via Bellman certificates, showing prior O((log T)^2) upper bounds are tight.