The $k$-Fold Matroid Secretary Problem

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\mathrm{/}\sqrt{k}))$-competitive algorithm when $\mathcal{M}$ is a $k$-uniform matroid. We generalize their result, giving a $(1-O(\sqrt{\log (n)\mathrm{/}k}))$-competitive algorithm when $\mathcal{M}$ is a $k$-fold matroid union.