### Abstract

We prove that for every proper minor-closed class M of Fp-representable matroids, there exists an O(1)-competitive algorithm for the matroid secretary problem onM. 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.

Original language | English |
---|---|

Pages (from-to) | 163-176 |

Number of pages | 14 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 34 |

Issue number | 1 |

DOIs | |

Publication status | Published - 9 Jan 2020 |

Externally published | Yes |

### Keywords

- Matroids
- Minors
- Online algorithms
- Tree decompositions

## Cite this

Huynh, T., & Nelson, P. (2020). The matroid secretary problem for minor-closed classes and random matroids.

*SIAM Journal on Discrete Mathematics*,*34*(1), 163-176. https://doi.org/10.1137/16M1107899