arXiv preprint ·
The Matroid Secretary Conjecture is True
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
Degree-Parameterized Analysis of Sampling-Based Online Matching
High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.