HackerPapers

arXiv:2609.14555cs.DS

The Matroid Secretary Conjecture is True

Sahil Singla

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least $1/4$. The algorithm only needs the number of elements in advance and independence-oracle access to subsets of already-arrived elements; it does not need to know the matroid upfront.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.GTComputer Science and Game Theory

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Sep 2026 to Sep 2026. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.