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}\). [16] gives a \((1 - O(1/\sqrt k))\)-competitive algorithm when \(\mathcal{M}\) is \(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.
Fields of Study & Subjects
Optimization and Search Problems
Advanced Graph Theory Research
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 91–99
- Publication date
- 1 January 2026
- Language
- EN