arXiv preprint ·
A 3.1462-Competitive Algorithm for Matroid Secretary
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 queries on already-arrived elements. Following his approach of maintaining a dynamically updated reference set, we introduce random deletions and a time-dependent acceptance rule, improving the competitive ratio to $C_*\approx3.1462$ in the same information model, where $C_*-\log C_*=2$. Our ordinal algorithm accepts every element of a fixed canonical optimum with probability exactly $1/C_*$ and uses $O(n^2)$ independence queries. The algorithm maintains a greedy reference solution, protects only accepted elements, and randomly deletes unaccepted reference-basis elements. A time-dependent acceptance rule makes the accepted set, conditional on the reference set, an independent thinning of its greedy basis. The resulting guarantee has a direct analytic proof.
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
Anchored Sequential Deliberation
ABM-SIRTEM: A Hybrid Agent-Based and Epidemiological Model for Pandemic Response
Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism
Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents
Intervention problems in the Linear Threshold Model: A general formulation and new results
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.