The matroid secretary problem for minor-closed classes and random matroids

Tony Huynh, Peter Nelson

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)163-176
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number1
DOIs
Publication statusPublished - 9 Jan 2020
Externally publishedYes

Keywords

  • Matroids
  • Minors
  • Online algorithms
  • Tree decompositions

Cite this