Source-linked AI summary
A 3.1462-Competitive Algorithm for Matroid Secretary
Hau Chan, Jianan Lin, Chenhao Wang
TL;DR
The matroid secretary problem asks how to select a high-weight independent set online under random arrivals and irrevocable decisions. This paper uses random deletions and time-dependent acceptance to maintain a thinned greedy reference set, achieving a 3.1462-competitive guarantee for arbitrary matroids. The optimal universal ratio remains open within the stated bounds.
Problem
The matroid secretary problem requires online selection of a high-weight independent set under uniformly random arrivals and immediate, irrevocable accept-or-reject decisions.
Source: §1 · p. 1Method
The algorithm randomly deletes unaccepted greedy-basis elements and uses time-dependent acceptance to maintain an exact conditional thinning of the reference set’s greedy basis.
Source: §1 · p. 2Results
Takeaways & Limitations
The algorithm gives an ordinal guarantee for arbitrary matroids using only n and independence queries on already-arrived elements.
Source: §1 · p. 2, §3 · p. 5The optimal universal competitive ratio remains open in [e ≈ 2.7182, 3.1462], and the optimal e guarantee is known only for linear matroids.
Source: §4 · p. 13
Abstract
from arXiv · showhide
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.
1 Introduction
The paper improves the general matroid secretary guarantee with a dynamically updated greedy reference set and a time-dependent acceptance rule. Its key analysis maintains an exact conditional-thinning distribution, yielding a 3.1462-competitive ordinal algorithm.
1 Introduction
- The problem combines random-order online selection with an independence constraint, requiring irrevocable choices that maximize expected weight relative to the full-information optimum.The matroid secretary problem generalizes single-choice and multiple-choice secretary problems.Source: §1 · p. 1
- Singla [13] gave the first 4-competitive guarantee for arbitrary matroids using n and arrived-element independence queries, while Abdi et al. [1] gave a 64-competitive algorithm when the matroid is known.Singla’s algorithm uses a virtual order and reversibly updated sample; his possible improvement to approximately 3.16 was left unverified.Source: §1 · pp. 1–3
- 3.1462 is the competitive ratio of the new algorithm for arbitrary matroids, and each canonical-optimum element is selected with probability exactly 1/C∗≈0.3178.It uses only n and independence-oracle access to already-arrived elements, with O(n^2) queries.Source: §1 · p. 2
- The algorithm protects accepted elements rather than every element in the reference basis, allowing unaccepted basis elements to be displaced or deleted.This addresses the earlier approach’s protection of virtual-past elements, including rejected sample elements.Source: §1 · p. 2
- The algorithm samples a rejected prefix, then randomly deletes unaccepted greedy-basis elements and accepts later arrivals under a time-dependent rule.Only accepted arrivals are inserted into the reference set.Source: §1 · p. 2
- At every fixed time, the reference set includes each element independently with probability p, while its greedy basis is independently thinned into the accepted set conditional on that reference.The thinning probability varies with time, unlike the fixed 1/2 probability used by Abdi et al. [1].Source: §1 · p. 2
2 Preliminaries
The preliminaries define the matroid setting, the canonical optimum, and the stronger per-element guarantee used in the analysis. Greedy scans also provide the exchange and deletion properties that motivate the algorithm’s updates.
2 Preliminaries
- The matroid secretary model fixes nonnegative weights and the matroid before a uniformly random arrival order; the algorithm knows n and can query independence only on arrived elements.The algorithm accepts or rejects each element immediately, and the accepted set must remain independent.Source: §2 · p. 3
- The canonical optimum O_w is the maximum-weight independent set returned by greedy selection with fixed label tie-breaking, and c-probability-competitiveness requires each element of O_w to be selected with probability at least 1/c.This per-element guarantee implies the expected-weight guarantee by nonnegativity and linearity of expectation.Source: §2 · pp. 3–4
- Every canonical-optimum element remains selected by the greedy scan when added to any set that omits it.This property follows because the element is outside the closure of the heavier elements that precede it.Source: §2 · p. 4
- When an inserted element is selected by greedy, the new basis either adds it or exchanges it for one unique existing basis element.Deleting a reference-basis element preserves the other basis members, possibly adding a replacement; these properties motivate the algorithm’s update rules.Source: §2 · p. 4
3 Algorithm and Analysis
This section presents Dynamic Thinning, which returns an independent set and accepts every element of a fixed canonical optimum with probability exactly 1/C*. Its analysis characterizes the evolving state through a conditionally thinned greedy reference basis and optimizes the resulting probability-competitive guarantee to a ratio of about 3.1462.
3 Algorithm and Analysis
- Each canonical-optimum element is accepted with probability exactly 1/C*≈1/3.1462, making Dynamic Thinning C*-competitive.The guarantee holds for every matroid secretary instance with n elements and nonnegative weights.Source: §3 · p. 5
3.1 The Algorithm
- The ordinal algorithm uses only n and independence queries on arrived elements, with at most n + 1 greedy scans and n(n + 1) oracle queries.Its additional computation is polynomial under the stated real-arithmetic sampling convention.Source: §3 · p. 5, §3.1 · pp. 6–7
- The algorithm protects accepted elements while unaccepted reference-basis elements can be displaced or randomly deleted; deletions change only the reference state.A time-dependent acceptance probability for rank-increasing arrivals works with the deletion process, while accepted elements remain in the reference basis.Source: §3.1 · pp. 5–6
3.2 Reference States and Arrival Order
- Conditional on the full reference-state partition, the accepted set is an independent (1 − q(t))-thinning of the greedy reference basis.The partition places each element independently in the reference set, the arrived-outside-reference set, or the unarrived set with probabilities p, t−p, and 1−t, respectively.Source: §3.2 · p. 8
- The proposed state probabilities satisfy the full forward system and yield the actual state law through the terminal time t=1.The argument verifies the equations on p≤t<1 and obtains the terminal law by taking the limit as t approaches 1.Source: §3.2 · p. 11
- At time t, elements independently enter X_t, Z_t, or U_t with probabilities p, t−p, and 1−t, while A_t conditionally independently retains each element of Greedy(X_t) with probability 1−q.The thinning law conditions on the current partition; conditioning instead on the initial sample, full arrival permutation, or all auxiliary times need not preserve it.Source: §3.2 · p. 11
3.3 Competitive Ratio
- For each fixed p, Dynamic Thinning is 1/γ(p)-probability-competitive, and this guarantee is exact on a positive-weight free matroid.On a free matroid, O=E and every element is accepted with probability exactly γ(p).Source: §3.3 · pp. 11–12
- C*≈3.1461932206, determined by C*−log C*=2, is attained at p*≈0.4659412724.The paper also gives rational choices p=1/2 and p=27/58, with competitive ratios 3.1640 and 3.1462, respectively.Source: §3.3 · p. 12
4 Conclusion
The conclusion presents a 3.1462-competitive algorithm for arbitrary matroids using only the element count and independence queries on arrived elements. The optimal universal ratio remains unresolved, and improving the fixed-rate Dynamic Thinning family requires changing its maintained distribution or update rules.
4 Conclusion
- 3.1462 is the competitive ratio of the algorithm for arbitrary matroids, using only the number of elements and independence queries on arrived elements.The authors describe the guarantee in the same information model as prior general-matroid work.Source: §4 · p. 13
- The algorithm protects accepted elements and deletes unaccepted reference-basis elements; time-dependent acceptance yields conditional thinning and an exact per-optimum-element selection probability.The resulting probability gives the competitive ratio.Source: §4 · p. 13
- The optimal universal competitive ratio remains open in [e ≈ 2.7182, 3.1462], and improving this fixed-rate family requires changing its maintained distribution or update rules.Within the fixed-rate Dynamic Thinning family, the selection formula is tight.Source: §4 · p. 13
- The authors disclose GPT-6 Astra’s role in generating the principal algorithmic constructions and proof arguments, manual finalization, and Codex assistance with manuscript revision.They state that they take responsibility for the mathematical claims and final content.Source: §4 · p. 13