The sharp matroid secretary conjecture
Let $M = (E, \mathcal{I})$ be a finite matroid. In the matroid secretary problem the algorithm knows $M$ in advance and may test the independence of any subset of $E$. An adversary fixes weights $w : E \to [0, \infty)$, hidden from the algorithm, and the elements then arrive in a uniformly random order $\pi$, independent of $w$. When $x$ arrives the algorithm learns $w(x)$ and must immediately and irrevocably accept or reject it, and the accepted set must always be independent. Let $$\operatorname{OPT}(M, w) = \max_{I \in \mathcal{I}} \sum_{x \in I} w(x).$$ No bound on running time is imposed, and the algorithm may use the numerical weights.
For the rank-one case, the classical secretary problem, the best achievable probability of selecting the heaviest element tends to $1/e$. Babaioff, Immorlica and Kleinberg gave an $O(\log k)$-competitive algorithm for matroids of rank $k$; Lachish, and Feldman, Svensson and Zenklusen, improved this to $O(\log \log k)$. In 2026 preprints, Singla gives an algorithm that accepts each element of a maximum-weight independent set with probability at least $1/4$, for every matroid, and Abdi, Banihashem, Hajiaghayi and Mittal, and independently Bérczi, Dughmi, Livanos, Soto and Verdugo, obtain the factor $1/e$ for linear matroids.
Problem. Does every finite matroid $M$ admit a randomized online policy $A_M$, chosen without knowing $w$, such that for every $w$ $$\mathbb{E}_{\pi, A_M}\Bigl[\sum_{x \in A_M(M, w, \pi)} w(x)\Bigr] \ge \frac{1}{e} \operatorname{OPT}(M, w),$$ the expectation being over the arrival order and the policy's randomness?
Source: Babaioff, Immorlica and Kleinberg (2007), Question 1, for a constant factor (the matroid secretary conjecture); the sharp factor 1/e, the strong matroid secretary conjecture, as stated by Soto, Turkieltaub and Verdugo (2021), who attribute both forms to Babaioff et al.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO, PR
- Keywords
- AIM Open Applied Problems, matroids, online algorithms, secretary problems
References
@inproceedings{babaioff2007,
author = {Babaioff, Moshe and Immorlica, Nicole and Kleinberg, Robert},
title = {Matroids, secretary problems, and online mechanisms},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA} 2007)},
publisher = {SIAM},
address = {Philadelphia, PA},
year = {2007},
pages = {434--443},
}
@article{babaioff2018,
author = {Babaioff, Moshe and Immorlica, Nicole and Kempe, David and Kleinberg, Robert},
title = {Matroid secretary problems},
journal = {J. ACM},
volume = {65},
number = {6},
year = {2018},
pages = {1--26},
doi = {10.1145/3212512},
}
@article{soto2021,
author = {Soto, Jos{\'e} A. and Turkieltaub, Abner and Verdugo, Victor},
title = {Strong algorithms for the ordinal matroid secretary problem},
journal = {Math. Oper. Res.},
volume = {46},
number = {2},
year = {2021},
pages = {642--673},
doi = {10.1287/moor.2020.1083},
eprint = {1802.01997},
archivePrefix = {arXiv},
}
@inproceedings{lachish2014,
author = {Lachish, Oded},
title = {{$O(\log\log \mathrm{Rank})$} competitive ratio for the matroid secretary problem},
booktitle = {2014 {IEEE} 55th Annual Symposium on Foundations of Computer Science ({FOCS})},
publisher = {IEEE},
year = {2014},
pages = {326--335},
doi = {10.1109/FOCS.2014.42},
}
@article{feldman2018,
author = {Feldman, Moran and Svensson, Ola and Zenklusen, Rico},
title = {A simple {$O(\log\log(\mathrm{rank}))$}-competitive algorithm for the matroid secretary problem},
journal = {Math. Oper. Res.},
volume = {43},
number = {2},
year = {2018},
pages = {638--650},
doi = {10.1287/moor.2017.0876},
}
@misc{singla2026,
author = {Singla, Sahil},
title = {The matroid secretary conjecture is true},
year = {2026},
eprint = {2609.14555},
archivePrefix = {arXiv},
}
@misc{abdi2026,
author = {Abdi, Hamed and Banihashem, Kiarash and Hajiaghayi, MohammadTaghi and Mittal, Danny},
title = {On the strong matroid secretary conjecture and beyond},
year = {2026},
eprint = {2609.19118},
archivePrefix = {arXiv},
}
@misc{berczi2026,
author = {B{\'e}rczi, Krist{\'o}f and Dughmi, Shaddin and Livanos, Vasilis and Soto, Jos{\'e} A. and Verdugo, Victor},
title = {The strong secretary conjecture is true for linear matroids},
year = {2026},
eprint = {2609.20797},
archivePrefix = {arXiv},
}
@misc{aim-sharp-matroid-secretary,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The sharp matroid secretary conjecture}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/330-sharp-matroid-secretary.md},
note = {Entry 330 at commit a153f46, 2026-10-13},
}
Resolution claims
This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-15 | Needs verification → Solution claimed | — | Recorded here: arXiv:2609.30421v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00404, "The sharp matroid secretary conjecture", clopen.solutions.