In the matroid secretary problem, elements $N := [n]$ of a matroid $\mathcal{M} \subseteq 2^N$ arrive in random order. When an element arrives, its weight is revealed and a choice must be made to accept or reject the element, subject to the constraint that the accepted set $S \in \mathcal{M}$. Kleinberg'05 gives a $(1-O(1/\sqrt{k}))$-competitive algorithm when $\mathcal{M}$ is a $k$-uniform matroid. We generalize their result, giving a $(1-O(\sqrt{\log(n)/k}))$-competitive algorithm when $\mathcal{M}$ is a $k$-fold matroid union.

翻译：在拟阵秘书问题中，拟阵 $\mathcal{M} \subseteq 2^N$ 的元素 $N := [n]$ 以随机顺序到达。当元素到达时，其权重被揭示，必须立即决定接受或拒绝该元素，且需满足接受集合 $S \in \mathcal{M}$ 的约束条件。Kleinberg'05 在 $\mathcal{M}$ 为 $k$-均匀拟阵时给出了 $(1-O(1/\sqrt{k}))$-竞争算法。本文推广了该结果，当 $\mathcal{M}$ 为 $k$-重拟阵并时，提出了 $(1-O(\sqrt{\log(n)/k}))$-竞争算法。