The Multiple-Choice Matroid Secretary Problem
Data Structures and Algorithms
Summary
The authors study a version of the secretary problem where multiple choices are allowed and the solution must respect matroid constraints. They propose algorithms that handle storing candidates online and then selecting the best final set offline, focusing on two approaches: multi-track and union-based. Their main result is an optimal algorithm for transversal matroids without capacity limits, matching the known best probabilities from the simpler classical problem. They also analyze algorithms for versions with capacity limits and extend their methods to other matroid types, providing explicit performance guarantees.
Authors
Matías Ortiz-Angel, José A. Soto
Abstract
We introduce and study the multiple-choice matroid secretary problem, denoted $(J,κ)$-MSP. For rank-one matroids and $κ=\infty$, it reduces to the classical secretary problem with $J$ choices. Elements arrive in uniformly random order. Algorithms may keep a candidate pool $\mathrm{AUX}$ feasible in the $J$-fold union matroid $\mathcal{M}^{(J)}$ satisfying $|\mathrm{AUX}|\le κ\cdot\mathrm{rank}(\mathcal{M})$. Finally, one extracts the maximum-weight independent subset of $\mathrm{AUX}$ in $\mathcal{M}$. This model separates online storage from the final feasible solution. We study two multiple-choice implementations: multi-track algorithms (maintaining $J$ independent sets of $\mathcal{M}$) and union-based algorithms (maintaining the pool directly in $\mathcal{M}^{(J)}$). Our main result is an exact optimal algorithm for transversal matroids in the uncapacitated $(J,\infty)$ setting. For fixed $J$, its probability-competitive ratio equals the optimal success probability of the classical $J$-choice secretary problem. Thus, rank-one instances are the worst case for the whole transversal class, and the optimal guarantee converges exponentially fast to $1$ as $J$ grows. We also analyze a simple single-threshold routing algorithm for capacitated transversal matroids with local capacities $b$ and global capacity $κ\cdot\mathrm{rank}(\mathcal{M})$. Its analysis provides explicit finite-parameter bounds and asymptotic formulas, showing how finite-rank loss caused by global capacity decays, and how $b$, $J$, and $κ$ interact. Finally, we instantiate the multi-track approach for $k$-column-sparse matroids (guarantee $1-O(e^{-J/(ke)})$) and the union-based approach for laminar matroids (guarantee $1-O(e^{-J/e})$).