The $k$-Fold Matroid Secretary Problem

Abstract

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.

11 pages, 1 figure, to appear in SOSA 2026