Preprint
Sep 2026
A 3.7321-Competitive Algorithm for Matroid Secretary
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence que...
Hau Chan, Jia-Nan Lin, Chen-Hao Wang
· 0 citations