Skip to content
Preprint

A 3.7321-Competitive Algorithm for Matroid Secretary

Sep 2026 · 0 citations · 13 references
Computer Science

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, we obtain an improved competitive ratio of $2+\sqrt3\approx3.7321$ in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least $2-\sqrt3$ and uses $O(n^2)$ independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.

View source

Similar papers

Preprint Oct 2026

A Faster Auction Algorithm for Weighted Matroid Intersection

This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$.

Tatsuya Terao · 1 citation
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
Preprint Sep 2026

Transposition achieves OPT$+O(1)$ in polynomial time for IID list update

It is proved that, for arbitrary $p and arbitrary initial orderings $\sigma$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

Clayton Mizgerd · 0 citations
Preprint Aug 2026

Derandomizing Karger's Contraction Algorithm for Matroids

Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a deterministic algorithm with the same exponent. If every contraction minor of rank at least $r_0$ of a matroid $M$ has cogirth-density ratio a...

Yu Cong, Chao Xu, Ya-Jie Zhao · 0 citations
Sep 2026

Faster Verification of PJR+ via Mincuts

It is demonstrated how to compute the largest value of $\alpha$ for which a committee still fails the axiom using this mincut formulation, and a direct mincut formulation of the problem on a bipartite graph is given.

Drew Springham · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.