The Matroid Secretary Problem for Minor-Closed Classes and Random Matroids
Tony Huynh, Peter Nelson · SIAM Journal on Discrete Mathematics · 2020
We prove that for every proper minor-closed class $\mathcal{M}$ of $\mathbb{F}_p$-representable matroids, there exists an $O(1)$-competitive algorithm for the matroid secretary problem on $\mathcal{M}$. This result relies on the extremely powerful matroid minor structure theory being developed by Geelen, Gerards, and Whittle. We also note that, for asymptotically almost all matroids, the matroid secretary algorithm that selects a random basis, ignoring weights, is $(2+o(1))$-competitive. In fact, assuming the conjecture that almost all matroids are paving, there is a $(1+o(1))$-competitive algorithm for almost all matroids.