CS Paper Radar

The Strong Secretary Conjecture is True for Linear Matroids

Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, Victor Verdugo

cs.DS ·submitted 2026-09-17 17:54 UTC · v2
theory

Abstract

We prove a $1/e$ guarantee for Matroid Secretary on linear matroids: each element of a fixed optimal basis is selected with probability at least $1/e$. This settles the strong secretary conjecture for this class of matroids. Our result holds both when the matroid is known in advance and when a linear representation is given online. In the known-matroid model, the result extends to fully modular extendable matroids. We also obtain $1/e$ guarantees for a more general model on linear matroids, both when the matroid is known and when its representation is revealed online. In XOS Matroid Secretary, agents with XOS valuations over the elements arrive in uniformly random order, and the algorithm must assign each arriving agent a bundle of elements. The bundles must be pairwise disjoint, and their union must be an independent set of the matroid. We obtain an expected total value of at least $1/e$ times the offline optimum. This model contains Group Matroid Secretary, in which the elements are adversarially partitioned into groups that arrive in uniformly random order, and the algorithm selects a subset of each arriving group. For this special case, we select each element of a fixed optimal basis with probability at least $1/e$

Closest papers

Nearest neighbours by meaning across the whole index.

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.77
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

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

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.73
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

Prophet Secretary for Matroids and XOS Valuations: A Separation at 1-1/e and a 0.6767 Guarantee for I.I.D. Weights

cs.DS cs.GT ·2026-11-04 ·Hossein Esfandiari, MohammadTaghi Hajiaghayi
similarity 0.73
Abstract

Ehsani, Hajiaghayi, Kesselheim, and Singla (SODA 2018) give $(1-1/e)$-competitive algorithms for matroid prophet-secretary and prophet-secretary with XOS valuation functions. In this work we show that these two guarantees have different limits. For every matroid, we give a randomized $(1-1/e+\varepsilon_0)$-competitive algorithm, where $\varepsilon_0=10^{-6}$. The guarantee holds for independent nonnegative values with finite expected optimum. For explicitly given finite distributions with rational values and probabilities, the algorithm has polynomial worst-case running time in the matroid independence-oracle model. The oracle tests whether a queried set is independent. The algorithm makes $O(N^4)$ such queries in expectation and $O(N^4\log(N+2))$ in the worst case, where $N$ is the number of elements. We further consider the i.i.d. version of this problem and provide a $0.6767$ competitive ratio for every matroid with i.i.d.\ nonnegative weights from a known distribution. This guarantee even holds in fixed arrival order (a.k.a. i.i.d. matriod prophet inequalities), even when the algorithm learns the order only as the elements arrive. For combinatorial auctions with XOS valuations, however, we show that $1-1/e$ is the optimal competitive ratio. We give an explicit family of finite instances showing that no online algorithm can guarantee a larger competitive ratio than $1-1/e$, even when the buyers' valuations are i.i.d., every additive clause has coefficients in $\{0,1\}$, and computation is unrestricted. Thus the matroid improvement exploits structure absent from general allocation with XOS valuations.

0.14

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 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

Constrained Fair Allocations via Partition Matroid Reductions

cs.GT ·2026-08-31 ·Benjamin Cookson, Nisarg Shah
published similarity 0.71
Abstract · Accepted to ACM EAAMO 2026

We study fair allocation of indivisible goods under additive valuations and matroid constraints. A challenging open question is whether a complete and feasible envy-free up to one good (EF1) allocation exists under every matroid that admits a complete and feasible allocation. The state-of-the-art result by Biswas and Barman [2018] positively resolves this question for partition matroids. Our first result positively resolves it for laminar matroids, which generalize partition matroids, when there are three agents. Our technique reduces this general existence question to finding an EF1 allocation satisfying a mild additional condition under a single finite-sized key laminar matroid, and we establish the required allocation by case analysis. We show that our technique somewhat extends to four agents, reducing the analogous problem to finding EF1 allocations under two finite-sized laminar matroids, although we are unable to establish their existence. We also use recent matroid decomposition results to establish EF1 existence under broader classes of matroids. Specifically, we show that EF1 allocations always exist under transversal matroids whenever a complete allocation is feasible, and obtain existence results for graphic matroids and gammoids under stronger assumptions.

0.48