The matroid secretary problem generalizes the secretary problem to selection subject to a matroid constraint (Babaioff et al. 2018). The elements of a finite matroid with fixed nonnegative weights arrive in a uniformly random permutation. An online algorithm decides irrevocably upon each arrival whether to accept the element. The accepted elements must be independent in the matroid, and the objective is to maximize the expectation value of their total weight relative to the maximum weight of an independent set. For a rank-one uniform matroid and distinct weights, the goal is to select the highest-weight element, as in the classical secretary problem.

The matroid secretary conjecture asks for a constant competitive ratio over all finite matroids. A stronger guarantee bounds the probability of accepting each element of a fixed canonical optimum, defined by a greedy algorithm that scans in decreasing weight with a fixed tie order. Abdi et al. (2026) report an ordinal algorithm that accepts those elements independently with probability each. The algorithm uses only comparisons of weights and initially needs only the number of elements. It makes an expected polynomial number of independence queries on subsets of arrived elements. The claimed competitive ratio is asymptotically optimal already for rank one. The authors credit GPT Astra with helping obtain the main algorithmic guarantees.

See also

Matroid, Online Algorithm, Secretary Problem

Explore with Wolfram|Alpha

References

Abdi, H.; Banihashem, K.; Hajiaghayi, M. T.; Huang, Z.; Mittal, D.; and Singla, S. "As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet." 6 Nov 2026. https://arxiv.org/abs/2611.08869v1.Babaioff, M.; Immorlica, N.; Kempe, D.; and Kleinberg, R. "Matroid Secretary Problems." J. ACM 65, Article 35, 2018. https://doi.org/10.1145/3212512.

Cite this as:

Weisstein, Eric W. "Matroid Secretary Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MatroidSecretaryProblem.html

Subject classifications