The matroid secretary problem for minor-closed classes and random matroids
The matroid secretary problem for minor-closed classes and random matroids
复制标题
小封闭类和随机拟阵的拟阵秘书问题
DOI：
--
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
P. Nelson
中科院分区：
文献类型：
--
作者：
T. Huynh;P. Nelson
证明了对于可在素域上表示的拟阵的每一个适当的小闭类$M$，存在一个针对$M$中的拟阵的常竞争拟阵秘书算法。这一结果依赖于由Geelen， Gerards和Whittle提出的非常强大的小行星小结构理论。
We prove that for every proper minor-closed class $M$ of matroids representable over a prime field, there exists a constant-competitive matroid secretary algorithm for the matroids in $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.