Preprint
Aug 2026
Graphic Matroid Secretary without the Graph
The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all...
Paul Dütting, R. P. Leme, Martin Pál et al.
· 5 citations