CS Paper Radar

Multilevel Dynamic Thinning for Matroid Secretary

Dennis Joyce

cs.DS ·submitted 2026-10-04 14:36 UTC · v1

Abstract

In the matroid secretary problem, weighted elements arrive in random order, and an online algorithm must irrevocably accept elements forming a high-weight independent set. Dynamic Thinning is a recent, conceptually simple $3.1462$-competitive algorithm for the matroid secretary problem that maintains a random reference set. Given this reference set, the elements in its maximum-weight independent subset have been accepted independently with a time-dependent probability. We extend this approach by replacing the single reference set with a finite hierarchy of nested reference sets. For every fixed $\eps>0$, the resulting algorithm is $(e+\eps)$-probability-competitive for arbitrary matroids, with $O_\eps(n^2)$ queries in the worst case.

Closest papers

Nearest neighbours by meaning across the whole index.

A 3.1462-Competitive Algorithm for Matroid Secretary

cs.DS cs.GT ·2026-09-15 ·Hau Chan, Jianan Lin, Chenhao Wang
highly cited similarity 0.81
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.

0.47

Settling the Matroid Secretary Problem

cs.DS ·2026-09-24 ·Zhiyi Huang
highly cited similarity 0.76
Abstract

This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.

0.34

The Matroid Secretary Conjecture is True

cs.DS cs.GT ·2026-09-13 ·Sahil Singla
highly cited similarity 0.76
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.

0.30

Graphic Matroid Secretary without the Graph

cs.DS ·2026-08-11 ·Paul Dütting, Renato Paes Leme, Martin Pál, Neel Patel
similarity 0.73
Abstract

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 information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

0.42

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet

cs.DS cs.GT ·2026-11-06 ·Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Zhiyi Huang, Danny Mittal +1 more
similarity 0.73
Abstract · This paper merges and extends arXiv:2609.14555, arXiv:2609.19118, and arXiv:2609.30421

We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios $e$ and $2$, respectively. Both ratios are optimal, even for rank-one matroids. For matroid secretary, our ordinal algorithm accepts the elements of the canonical optimum independently, each with probability $1/e$. It needs only the number of elements in advance and uses an expected polynomial number of independence queries on arrived elements. For single-sample matroid prophet inequalities, our algorithm uses one sample per independent value distribution and $O(n^2)$ independence queries on a known $n$-element matroid. It works for every arrival order fixed independently of the samples, values, and algorithmic randomness. The selected elements and their values have exactly the joint distribution obtained by independently retaining each element--value pair in the canonical optimum of a fresh product draw with probability $1/2$. Our main algorithms maintain a reference state whose greedy solution contains every accepted element. Its updates, made even after rejections, preserve exact distributional invariants. A short reversible-update argument gives a $4$-probability-competitive secretary algorithm, already resolving the original conjecture; a related invariant gives the optimal single-sample prophet inequality. For secretary, we characterize the distributions achievable by ordinal algorithms through a finite polytope. A continuous-time formulation then lets us design an accepted-set distribution achieving the optimal ratio $e$ and realize it efficiently. We also obtain guarantees for matroid intersections.

0.39

A Faster Auction Algorithm for Weighted Matroid Intersection

cs.DS ·2026-10-01 ·Tatsuya Terao
similarity 0.73
Abstract · 17 pages. In this version, we have completely rewritten the proof, which is now simpler and easier to follow, and improved the clarity and p…

We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19], Chekuri--Quanrud~[SODA'16], Quanrud~[ICALP'24], and Dudeja--Grilnberger~[IPCO'26] has developed efficient $(1-\varepsilon)$-approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size $n$, computes a $(1-\varepsilon)$-approximate maximum-weight common independent set using $O(n \varepsilon^{-2} \log^2(n))$ independence-oracle queries. 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$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang--Kobayashi~['26].

0.08

On the Strong Matroid Secretary Conjecture and Beyond

cs.DS ·2026-09-16 ·Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
theoryhot directionhighly cited similarity 0.73
Abstract

The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $α$ into a secretary ratio $α^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.

0.46

A Refined Analysis for Matroid Secretary with Submodular Objectives

cs.DS ·2026-10-08 ·Dennis Joyce
similarity 0.72
Abstract

We study the matroid secretary problem with a nonnegative monotone submodular objective. Elements arrive in uniformly random order, and every acceptance decision is immediate and irrevocable. We give an $8.699$-competitive algorithm for arbitrary matroids. The algorithm first rejects a randomly sized initial segment of the arrival sequence as a learning set and runs submodular greedy on all elements in this set. Each later element receives a fixed weight equal to the marginal value it would have when inserted into the stored greedy sequence. On these fixed weights, the algorithm runs a linear-objective matroid secretary subroutine. The algorithm uses $O(nr)$ value queries and $O(n^2)$ independence queries, where $r$ is the matroid rank.

0.05