Preprint
Sep 2026
On the Strong Matroid Secretary Conjecture and Beyond
The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven el...
Hamed Abdi, Kiarash Banihashem, Mohammadtaghi Hajiaghayi et al.
· 5 citations
· ⚡1