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.
The matroid secretary problem for minor-closed classes and random matroids / Huynh, T.; Nelson, P.. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 34:1(2020), pp. 163-176. [10.1137/16M1107899]
The matroid secretary problem for minor-closed classes and random matroids
Huynh T.;
2020
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.