betaFeedback

WorksComputer Science

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

Abstract

We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios ee and 22, 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/e1/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(n2)O(n^2) independence queries on a known nn-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/21/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 44-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 ee and realize it efficiently. We also obtain guarantees for matroid intersections.

Introduction

The classic secretary problem [26, 54] asks us to select the largest of nn distinct values revealed in uniformly random order, with immediate and irrevocable decisions. Rejecting roughly the first n/en/e values and then selecting the next value larger than all earlier ones gives the asymptotically optimal success probability 1/e1/e. Motivated by applications in auction design, Hajiaghayi, Kleinberg, and Parkes [38] and Kleinberg [45] studied the generalization in which up to rr values may be selected. Babaioff, Immorlica, and Kleinberg [11], with Kempe in the journal version [13], introduced the matroid secretary problem: fixed nonnegative values arrive in uniformly random order, and the selected elements must form an independent set of a matroid. Does such a constraint make online selection any harder than choosing a single element?

Matroids are natural constraints for this question. Offline, decreasing-value greedy finds a maximum-value independent set; indeed, among downward-closed systems, matroids are exactly those for which greedy is optimal for every nonnegative value assignment [27]. An algorithm is cc-competitive, for c≥1c \ge1, if its expected value is at least 1/c1/c times the offline optimum.

The matroid secretary conjecture [11] asks whether a universal constant suffices for every matroid; its strong form asks for the optimal constant ee, matching rank one. Before the results presented here, the best general guarantee was O(log⁡log⁡r)O(\log\log r), where rr is the matroid rank [51, 32]. This bound had stood since 2014, despite constant guarantees for graphic [11], laminar [43], and transversal [23] matroids, among many other classes (see Table 1). Natural greedy and partition-based approaches also face provable barriers [7, 2].

A related question concerns the information needed for online selection. In a matroid prophet inequality, the values are independent draws from known distributions, and the arrival order may be any fixed order. Kleinberg and Weinberg [50] gave a 2-competitive algorithm for every matroid, matching the classical single-element prophet inequality [49]. In the single-sample version [3], the distributions are unknown and the algorithm receives only one independent sample from each. For rank-one matroids, one sample per distribution already suffices for the optimal ratio 2 [62]. For general matroids, however, constant ratios were known only with polylogarithmically many samples per distribution [29, 34]. Does one sample suffice for a constant competitive ratio, or even for the optimal ratio 2? A positive answer would also resolve the matroid secretary conjecture for known matroids, by Li’s reduction [29] (Appendix § 13).

We resolve both problems with optimal ratios ee and 2, matching the rank-one guarantees. Since natural greedy rules that compare arrivals with a fixed sample can fail (Appendix § 9), our algorithms maintain a reference state whose greedy solution contains every accepted element, updating it even after rejections to preserve an exact distributional invariant. Our secretary algorithms use only ordinal information: the relative order of observed values. Moreover, our optimal algorithm accepts each element of the canonical optimum8 independently with probability 1/e1/e. Such a per-element guarantee of 1/c1/c, called cc-probability-competitiveness, implies ordinary cc-competitiveness.

Results

Theorem 1.1 (Optimal matroid secretary; informal Theorem 6.1). For every nn-element matroid revealed online, there is an ordinal secretary algorithm that accepts the elements of the canonical optimum independently, each with probability 1/e1/e. Knowing only nn in advance, it uses an expected polynomial number of independence queries on subsets of arrived elements.

Our second result considers the standard single-sample prophet model with an oblivious arrival order: the matroid and one independent sample per element are given before arrivals.

Theorem 1.2 (Optimal single-sample matroid prophet inequality; informal Theorem 3.1). For every known matroid and independent nonnegative value distributions, one independent sample from each distribution suffices for a 2-competitive algorithm using comparisons and O(n2)O(n^2) independence queries. The arrival order may be any fixed order independent of the samples, values, and algorithmic randomness; the algorithm need not know that order.

More strongly, its accepted elements and values are distributed exactly as an independent half-sample of the canonical optimum of fresh independent values, so it obtains exactly half the expected offline optimum.

A short combinatorial argument proves the original matroid secretary conjecture (§ 2).

Theorem 1.3 (Combinatorial matroid secretary; informal Theorem 2.2). For every nn-element matroid revealed online, there is an ordinal secretary algorithm that accepts each element of the canonical optimum with probability at least 1/41/4. Knowing only nn in advance, it uses O(n2)O(n^2) independence queries on subsets of arrived elements.

Characterizing online acceptance distributions. For a known matroid, we also show that a finite polytope exactly characterizes the conditional accepted-set distributions of ordinal secretary algorithms (Theorem 4.1). Its continuous-time version turns algorithm design into distribution design: every family satisfying its constraints is realized online. Constructing one such family already resolves the strong matroid secretary conjecture; we then give an efficient implementation (Theorems 5.2 and 6.1). The same characterization also gives exact LPs for two benchmarks among ordinal algorithms (§ 4.2): the optimal per-element selection probability (probability competitiveness) and the best expected-value fraction (ordinal competitiveness). These differ even on uniform matroids: for rank kk and n≥2kn \ge2k, the first is 1−Θ(log⁡k/k)1-\Theta(\sqrt{\log k/k}) as k→∞k \to\infty, whereas ordinal algorithms achieve expected-value fraction 1−O(k−1/2)1-O(k^{-1/2}) (Theorem 7.1). The matching lower bound resolves a question of Soto, Turkieltaub, and Verdugo [66].

Finite-size guarantees and extensions. For linear matroids known in advance, one can beat 1/e1/e for every finite n≥2n \ge2: a separate construction selects each optimum element with the classical rank-one success probability for nn elements (Theorem 7.2). Computations on small matroids suggest the same finite-size comparison for ordinal competitiveness more generally (Appendix § 11). Beyond a single matroid, combining our reference-set method with the preprocessing of Feldman, Svensson, and Zenklusen [33] gives ratio 8k2(k+1)8k^2(k+1) for intersections of kk matroids (Theorem 7.3), avoiding the exponential dependence on kk in their general combination bound.

Technical overview

Inserting an optimum element into a greedy solution displaces at most one element, its exchange partner. If this partner were fixed independently of a uniformly random processing order, then with probability 1/21/2 the optimum element would precede it and could be accepted safely. But the partner depends on the algorithm’s state, which depends on the order. Instead, our algorithms maintain a reference state whose greedy solution contains every accepted element, and update it even after rejections so that the state seen by any fixed element, its snapshot, has an explicit distribution.

Reversible updates (§ 2). The combinatorial algorithm of Theorem 1.3 first rejects a random half-sample, which becomes the reference set. It then tries to insert each real arrival and, interleaved with these, to delete each sample element, updating only when greedy membership of every previously processed element is preserved. This test is symmetric, so every update can be undone: for any fixed processing order, the updates merely permute the equally likely initial samples. Hence each snapshot is uniform and independent of the processing order, and conditioning on it fixes the exchange partner without biasing their relative order. An optimum element is a real arrival with probability 1/21/2 and is then accepted with probability at least 1/21/2, giving 1/41/4.

Exchangeable values (§ 3). The prophet algorithm of Theorem 1.2 stores one value per element, initially its sample, and each arrival proposes replacing its sample by its real value. If the update would remove a processed element from the greedy basis, that element’s acceptance blocks it and its rejection forces it; otherwise a fair coin decides. The arrival is accepted if the update occurs and it belongs to the new basis. By exchangeability of sample and real values, the stored values remain a fresh product draw, and the accepted set a half-sample of its processed greedy elements.

Distributions as algorithms (§ 4). For the optimal ratio ee, we reverse the approach: design the accepted-set distributions first, and then realize them online. In a continuous-time formulation, two linear conditions characterize which distributions are realizable: capacity, which prevents moving more probability mass than a state contains, and consistency, which ensures that the transitions produce the prescribed distributions. Every feasible family is realized by an explicit rule (Theorem 4.4), so it suffices to construct one.

Survivor distributions (§ 5). We construct this family from an offline experiment with independent auxiliary arrival times: sample each element independently with probability 1/e1/e, and then thin the sample’s greedy solution to obtain the survivors. The thinning probabilities are motivated by the rank-one analysis and preserve every sampled global optimum element. The survivors therefore form an independent set and include each optimum element independently with probability 1/e1/e. The main obstacle is showing that this family is feasible. Consistency follows from a direct calculation as time advances. The crux is capacity: for every possible preceding accepted set, there must be enough probability mass to support the next acceptance. We prove it by induction after removing the largest element, comparing the survivor experiment with the same experiment in the matroid contracted by the arriving element. The rule realizing this family (Algorithm 3) already resolves the strong matroid secretary conjecture (Theorem 5.2).

From proof to efficient algorithm (§ 6). This rule needs probabilities of entire survivor sets, which we do not know how to compute efficiently. We therefore turn the capacity proof into a sampler: inductive comparisons become recursive calls, and unused mass becomes rejection. The sampler needs the auxiliary randomness conditioned on the accepted set, so we maintain a sample of it, one coordinate per element. Forward updates make new acceptances survive; reverse updates prevent old rejections from surviving. A continuous snapshot argument shows these updates keep the sample correctly distributed, giving an expected-polynomial-time algorithm (Theorem 1.1).

Related work and roadmap

Matroid secretary and related models. For general matroids, the guarantee improved from O(log⁡r)O(\log r) [11] to O(log⁡r)O(\sqrt{\log r}) [19] and then to O(log⁡log⁡r)O(\log\log r) [51, 32]; Table 1 lists progress on special classes. Constant guarantees were known in models that weaken the adversary: free-order secretary [44, 3], where the algorithm chooses the order; randomly assigned values [65, 37]; and prophet secretary [28], with known value distributions.

Sample-based prophet inequalities. Beyond rank one [62], single-sample guarantees were known for several matroid classes and matchings [18]. For general matroids, [29] obtained ratio 4+ε4+\varepsilon using Oε(log⁡4n)O_{\varepsilon}(\log^{4} n) samples per distribution. Feldman, Svensson, and Zenklusen [34] reduced this to Oε(log⁡n+log⁡rlog⁡2log⁡r)O_{\varepsilon}(\log n+\log r\log^{2}\log r) samples with the same ratio. Both handle an almighty adversary, which sees the samples, values, and algorithmic randomness before choosing the order. We assume an oblivious order. Complementing Li’s reduction, Azar, Kleinberg, and Weinberg [3] convert order-oblivious secretary algorithms, whose guarantee survives an arbitrary order after a random initial sample, into single-sample prophet algorithms with the same ratio.

Matroid classGuarantees and references
General matroidsO(log⁡log⁡r)O(\log\log r) [51, 32] ⟶eP\longrightarrow\mathrm{e}^{\mathrm{P}} (this paper, Theorem 6.1).
Rank one / partitione\mathrm{e} [54, 26, 12].
Uniform (rank rr)O(1)O(1) [38]; 1+O(r−1/2)1 + O(r^{-1/2}) [45]; [1+O(log⁡r/r)]P[1 + O(\sqrt{\log r/r})]^{\mathrm{P}} [66]; finite-rank refinements [14, 17, 4].
Truncated partitionO(1)O(1) [11, 13]; also covered by laminar results.
Transversal1616 [23] ⟶8\longrightarrow8 [47] ⟶e\longrightarrow\mathrm{e} [48]; eP\mathrm{e}^{\mathrm{P}} [66].
LaminarO(1)O(1) [43]; 1/0.0531/0.053 [40]; 33e3\sqrt{3}\mathrm{e} [44]; 9.69.6 [57]; (33)P(3\sqrt{3})^{\mathrm{P}} [66]; 4.754.75 [41]; [1/(1−ln⁡2)]P[1/(1-\ln2)]^{\mathrm{P}} [15].
Graphic1616 [11]; 3e3\mathrm{e} [8]; 2e2\mathrm{e} [47]; 4P4^{\mathrm{P}} [66]; (1/0.2504)P(1/0.2504)^{\mathrm{P}} [15]; 3.953.95 [10].
Simple / high-girth graphicSimple: 3.773.77 [10], (1/0.2693)P(1/0.2693)^{\mathrm{P}} [15]; girth gg: e+og(1)\mathrm{e}+o_g(1) [10].
Cographic; regular / MFMC3e3\mathrm{e} [65]; 9e9\mathrm{e} for regular and max-flow min-cut [21].
Hypergraphic; matching4P4^{\mathrm{P}} for both [66]; matching matroids have a vertex ground set.
kk-column-sparse; kk-framedkek\mathrm{e} for column-sparse [65]; [kk/(k−1)k−1]P[k^{k}/(k-1)^{k-1}]^{\mathrm{P}} for both (k≥2k \ge2) [66].
Gammoids[μμ/(μ−1)μ−1]P[\mu^{\mu}/(\mu-1)^{\mu-1}]^{\mathrm{P}} for exchangeability μ≥2\mu\ge2; semiplanar: (44/3)P(4^{4}/3)^{\mathrm{P}} [66].
Rank two(1/0.3462)P(1/0.3462)^{\mathrm{P}} [15]; all rank-two matroids.
Density / cocircuitsγ(M)\gamma(\mathcal{M}); cc if each nonloop lies in a cocircuit of size ≤c\le c [65].
Paving; almost all matroids1+O(r−1/2)1 + O(r^{-1/2}) for paving; 2+o(1)2 + o(1) for almost all labelled matroids [39].
Proper minor-closed C\mathcal{C}OC(1)O_{\mathcal{C}}(1) over Fp\mathbb{F}_p (fixed prime pp), under a structural hypothesis [39].
kk-fold unions1+O(log⁡n/k)1 + O(\sqrt{\log n/k}) for k≫log⁡nk \gg\log n [36].
Graphic, arrived-elements-only3636 [24].

Table 1. Earlier guarantees and our optimal general-matroid ratio. P denotes a per-element probability guarantee. Some results require advance knowledge of the matroid or its representation. Parameters μ\mu and γ(M)\gamma(\mathcal{M}) are defined in the cited works.

LP and distributional approaches. Buchbinder, Jain, and Singh [14] give finite LP characterizations for classical and multiple-choice secretary problems; Chan, Chen, and Jiang [17] develop continuous LPs for these variants. These LPs track only the number of accepted elements, which suffices under cardinality constraints; for general matroids, feasibility depends on the accepted set itself, so our polytope tracks distributions over accepted sets. Random-order contention resolution [6, 55] provides related per-element guarantees, and Dughmi [25] establishes an equivalence between matroid secretary and correlated random-order contention resolution. Aminian, Niazadeh, and Nuti [5] study stationary online contention resolution schemes, whose output distribution is independent of arrival order. Our characterization instead conditions on the observed elements and their relative value order, averaging over the arrival order.

Concurrent and subsequent work. The linear-matroid guarantee, including the finite-size probabilities in Theorem 7.2, was obtained independently in [9]. Building on Singla’s preprint [64], Chan, Lin, and Wang [20] improved the general-matroid competitive ratio from 4 to ≈ 3.1462. OpenAI [58] subsequently obtained a constant-competitive single-sample matroid prophet inequality against the stronger almighty adversary.

Roadmap. § 2 and § 3 prove the 4-competitive secretary and optimal single-sample prophet guarantees. § 4 to § 6 develop the polyhedral characterization, the optimal survivor distributions, and their efficient implementation, respectively. § 7 gives finite-size results and extensions. AI models played a material role in developing the main algorithmic guarantees; the AI methodology statement describes this role. The appendices contain examples, deferred proofs, and computations.

Matroid Secretary via Reversible Updates

We begin with a combinatorial 4-probability-competitive algorithm for matroid secretary. Its proof illustrates two ideas that will recur: protect irrevocable decisions through a changing greedy solution, and make the updates to a reference state reversible, so that they preserve a useful distribution.

Preliminaries

Fix a matroid M=(V,I)\mathcal{M}=(V,\mathcal{I}) with nonnegative values vev_e. Ties are broken by a fixed order of element labels, independent of arrival order; “larger” and “smaller” refer to this tie-broken value order. Write T+e=T∪{e}T+e=T\cup\{e\}, T−e=T∖{e}T-e=T\setminus\{e\}, and v(A)=∑e∈Avev(A)=\sum_{e\in A}v_e. For T⊆VT\subseteq V, let Greedy⁡(T)\operatorname{Greedy}(T) be the output of greedy, which scans TT in decreasing value order and adds each element that keeps the current set independent. Greedy includes zero-valued elements whenever possible, so Greedy⁡(T)\operatorname{Greedy}(T) is a basis of the restriction to TT; this does not change the optimum value.

The rank of TT is the largest size of an independent subset of TT. An element is spanned by TT if adding it does not increase the rank; the closure cl⁡(T)\operatorname{cl}(T) is the set of all such elements, and an element spanned by ∅\varnothing is a loop. The elements greedy selects from a prefix PP of its scan span PP, so an element is selected precisely when the elements preceding it do not span it, and greedy selects exactly rank⁡(P)\operatorname{rank}(P) elements from PP. We use the following standard consequences [27, 16, 63].

Lemma 2.1 (Greedy monotonicity and one-element sensitivity). With fixed tie-breaking, the following properties hold.

(i) If e∈T⊆Ve\in T\subseteq V and e∈Greedy⁡(V)e\in\operatorname{Greedy}(V), then e∈Greedy⁡(T)e\in\operatorname{Greedy}(T). More generally, reducing other values while keeping a selected element’s value fixed does not remove it from greedy.

(ii) For e∉Te\notin T, the set Greedy⁡(T+e)\operatorname{Greedy}(T+e) is either Greedy⁡(T)\operatorname{Greedy}(T), Greedy⁡(T)+e\operatorname{Greedy}(T)+e, or (Greedy⁡(T)−f)+e(\operatorname{Greedy}(T)-f)+e for one f∈Greedy⁡(T)f\in\operatorname{Greedy}(T).

(iii) Changing one value on a fixed ground set either leaves the greedy basis unchanged or exchanges that element with one other element. An increase can only bring the changed element into the basis; a decrease can only remove it.

Proof. For (i), restricting the ground set or reducing other values can only shrink the selected element’s predecessor set. A subset cannot span an element that the larger set did not span.

For (ii), inserting ee into the scan can only add a predecessor to each old element. Thus no old element can enter greedy, and the only possible new member is ee. Greedy returns bases of TT and T+eT+e, whose ranks differ by at most one, giving the three possibilities. For (iii), increasing the value of ee shrinks its predecessor set and can only add ee to the others’, so only ee can enter and only other elements can leave; since both bases have the same size, any change is one exchange. A decrease is symmetric.

The algorithm

Model. The n=∣V∣n = |V| elements arrive in a uniformly random order. On each arrival, the algorithm observes the element and its value and must irrevocably accept or reject it before the next arrival. The accepted set must be independent. The number nn is known; values and the matroid are otherwise unknown, and independence queries may involve only observed elements. A cc-probability-competitive algorithm accepts each e∈Greedy⁡(V)e \in\operatorname{Greedy}(V) with probability at least 1/c1/c. An algorithm is ordinal if it uses values only through their tie-broken order.

Algorithm. The algorithm first rejects and stores a random initial sample SS, with ∣S∣∼Bin⁡(n,1/2)|S| \sim\operatorname{Bin}(n,1/2); call the remaining arrivals real. It then runs nn processing steps, each either receives the next real arrival or internally processes the next stored sample element. Its reference state is a configuration C⊆VC \subseteq V, initially SS; it also maintains the set FF of processed elements, initially empty. A sample element enters FF only when internally processed and remains rejected. Write C⊕eC \oplus e for adding ee to CC if absent and removing it if present, so (C⊕e)⊕e=C(C \oplus e) \oplus e = C. Processing ee proposes C′=C⊕eC' = C \oplus e, a deletion for a sample element and an insertion for a real arrival. The update occurs exactly when it passes the preservation test: the greedy membership of every element of FF remains unchanged.

References

  1. [1]Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal. On the Strong Matroid Secretary Conjecture and Beyond, 2026. arXiv:2609.19118.arxiv.org/abs/2609.19118
  2. [2]Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid partition property and the secretary problem. In 14th Innovations in Theoretical Computer Science Conference, ITCS, volume 251 of LIPIcs, pages 2:1–2:9, 2023.
  3. [3]Pablo Daniel Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet inequalities with limited information. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1358–1377. SIAM, 2014.
  4. [4]Susanne Albers and Leon Ladewig. New results for the k-secretary problem. Theoretical Computer Science, 863:102–119, 2021. Full version; preliminary version in ISAAC 2019.
  5. [5]Mohammad Reza Aminian, Rad Niazadeh, and Pranav Nuti. Stationary online contention resolution schemes, 2026. arXiv:2603.21532.arxiv.org/abs/2603.21532
  6. [6]Marek Adamczyk and Michal Wlodarczyk. Random order contention resolution schemes. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 790–801. IEEE Computer Society, 2018.arxiv.org/abs/1804.02584
  7. [7]Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, and S. Matthew Weinberg. Formal barriers to simple algorithms for the matroid secretary problem. In Web and Internet Economics - 17th International Conference, WINE, Proceedings, volume 13112 of Lecture Notes in Computer Science, pages 280–298. Springer, 2021.arxiv.org/abs/2111.04114
  8. [8]Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar. Secretary problems: Weights and discounts. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1245–1254, 2009.
  9. [9]Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, José A. Soto, and Victor Verdugo. The Strong Secretary Conjecture is True for Linear Matroids, 2026. arXiv:2609.20797.arxiv.org/abs/2609.20797
  10. [10]Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating competitive ratio 4 for graphic matroid secretary. In 33rd Annual European Symposium on Algorithms (ESA 2025), volume 351, pages 52:1–52:16, 2025.arxiv.org/abs/2501.08846
  11. [11]Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434–443, 2007.DOI
  12. [12]Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 4627, pages 16–28, 2007.DOI
  13. [13]Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Matroid secretary problems. Journal of the ACM, 65(6):35:1–35:26, 2018.DOI
  14. [14]Niv Buchbinder, Kamal Jain, and Mohit Singh. Secretary problems via linear programming. Mathematics of Operations Research, 39(1):190–206, 2014.
  15. [15]Kristóf Bérczi, Vasilis Livanos, José A. Soto, and Victor Verdugo. Matroid secretary via labeling schemes. In Integer Programming and Combinatorial Optimization (IPCO), pages 128–141, 2025. Full version arXiv:2411.12069v2, 2025; first preprint 2024.arxiv.org/abs/2411.12069
  16. [16]Richard A. Brualdi. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society, 1(2):161–167, 1969.DOI
  17. [17]T.-H. Hubert Chan, Fei Chen, and Shaofeng H.-C. Jiang. Revealing optimal thresholds for generalized secretary problem via continuous LP: Impacts on online $K$-item auction and bipartite $K$-matching with random arrival order. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1169–1188, 2015.
  18. [18]Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiff enhäuser. Single-sample prophet inequalities via greedy-ordered selection. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1298–1325. SIAM, 2022.
  19. [19]Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1702–1712, 2012.
  20. [20]Hau Chan, Jianan Lin, and Chenhao Wang. A 3.1462-Competitive Algorithm for Matroid Secretary, 2026. arXiv:2609.17782, version 2.arxiv.org/abs/2609.17782
  21. [21]Michael Dinitz and Guy Kortsarz. Matroid secretary for regular and decomposable matroids. SIAM Journal on Computing, 43(5):1807–1830, 2014.
  22. [22]Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiff enhäuser, and Sahil Singla. Online combinatorial allocations and auctions with few samples. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1231–1250. IEEE, 2024.
  23. [23]Nedialko B. Dimitrov and C. Greg Plaxton. Competitive weighted matching in transversal matroids. In Automata, Languages and Programming (ICALP), Part I, volume 5125 of Lecture Notes in Computer Science, pages 397–408, 2008.
  24. [24]Paul Dütting, Renato Paes Leme, Martin Pál, and Neel Patel. Graphic matroid secretary without the graph, 2026. arXiv:2608.11413.arxiv.org/abs/2608.11413
  25. [25]Shaddin Dughmi. From contention resolution to matroid secretary and back. SIAM J. Comput., 54(3):585–624, 2025.
  26. [26]E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics Doklady, 4:627–629, 1963.
  27. [27]Jack Edmonds. Matroids and the greedy algorithm. Mathematical programming, 1(1):127–136, 1971.DOI
  28. [28]Soheil Ehsani, Mohammad'Taghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. SIAM J. Comput., 53(6):1641–1662, 2024.
  29. [29]Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Sample-based matroid prophet inequalities. In Proceedings of the 25th ACM Conference on Economics and Computation, EC, page 781. ACM, 2024.arxiv.org/abs/2406.12799
  30. [30]Tara Fife and James Oxley. Generalized laminar matroids. European Journal of Combinatorics, 79:111–122, 2019.arxiv.org/abs/1801.06882
  31. [31]Matthew Faw, Sahil Singla, and Yifan Wang. Online allocation using few samples, 2026. arXiv:2609.17343.arxiv.org/abs/2609.17343
  32. [32]Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1189–1201, 2015.
  33. [33]Moran Feldman, Ola Svensson, and Rico Zenklusen. A framework for the secretary problem on the intersection of matroids. SIAM J. Comput., 51(3):766–819, 2022. Preprint: arXiv:1704.02608.
  34. [34]Moran Feldman, Ola Svensson, and Rico Zenklusen. Nearly tight sample complexity for matroid online contention resolution. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 4692–4711. SIAM, 2026.arxiv.org/abs/2507.09507
  35. [35]Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. SIAM J. Comput., 47(2):330–366, 2018.
  36. [36]Rishi Gujjar, Kevin Hua, Robert Kleinberg, and Frederick V. Qiu. The k-fold matroid secretary problem. In Proceedings of the 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 91–99. SIAM, 2026.arxiv.org/abs/2512.06611
  37. [37]Shayan Oveis Gharan and Jan Vondrák. On variants of the matroid secretary problem. Algorithmica, 67(4):472–497, 2013.
  38. [38]MohammadTaghi Hajiaghayi, Robert D. Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 71–80, 2004.DOI
  39. [39]Tony Huynh and Peter Nelson. The matroid secretary problem for minor-closed classes and random matroids. SIAM Journal on Discrete Mathematics, 34(1):163–176, 2020.
  40. [40]David Harris and Manish Purohit. Improved algorithms and analysis for the laminar matroid secretary problem, 2013. arXiv:1301.4958.arxiv.org/abs/1301.4958
  41. [41]Zhiyi Huang, Zahra Parsaeian, and Zixuan Zhu. Laminar matroid secretary: Greedy strikes back. In 32nd Annual European Symposium on Algorithms (ESA 2024), pages 73:1–73:8, 2024.arxiv.org/abs/2308.09880
  42. [42]Zhiyi Huang. Settling the Matroid Secretary Problem, 2026. arXiv:2609.30421.
  43. [43]Sungjin Im and Yajun Wang. Secretary problems: Laminar matroid and interval scheduling. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265–1274, 2011.
  44. [44]Patrick Jaillet, José A. Soto, and Rico Zenklusen. Advances on matroid secretary problems: Free order model and laminar case. In Integer Programming and Combinatorial Optimization (IPCO), volume 7801 of Lecture Notes in Computer Science, pages 254–265, 2013.arxiv.org/abs/1207.1333
  45. [45]Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630–631, 2005.DOI
  46. [46]Thomas Kesselheim, Marco Molinaro, Kalen Patton, and Sahil Singla. Online algorithms via minimax and posterior matching. In Proceedings of the 67th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2026. To appear. arXiv:2608.01616.arxiv.org/abs/2608.01616
  47. [47]Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In Automata, Languages and Programming (ICALP), Part II, volume 5556 of Lecture Notes in Computer Science, pages 508–520, 2009.arxiv.org/abs/0807.1139
  48. [48]Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Algorithms – ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 589–600, 2013.
  49. [49]Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. In J. Kuelbs, editor, Probability on Banach Spaces, volume 4 of Advances in Probability and Related Topics, pages 197–266. Marcel Dekker, New York, 1978.
  50. [50]Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 123–136. ACM, 2012.
  51. [51]Oded Lachish. O(log log Rank) competitive ratio for the matroid secretary problem. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 326–335, 2014.
  52. [52]Lucien Le Cam. An approximation theorem for the Poisson binomial distribution. Pacific J. Math., 10(4):1181–1197, 1960.
  53. [53]Wenzheng Li. Personal communication, 2024.
  54. [54]D. V. Lindley. Dynamic programming and decision theory. Applied Statistics, 10(1):39–51, 1961.
  55. [55]Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In 26th Annual European Symposium on Algorithms, ESA, volume 112 of LIPICs, pages 57:1–57:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  56. [56]Dillon Mayhew and Gordon F. Royle. Matroids with nine elements. J. Combin. Theory Ser. B, 98(2):415–431, 2008.arxiv.org/abs/math/0702316
  57. [57]Tengyu Ma, Bo Tang, and Yajun Wang. The simulated greedy algorithm for several submodular matroid secretary problems. Theory of Computing Systems, 58(4):681–706, 2016. Preliminary version appeared at STACS 2013.
  58. [58]OpenAI. One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary. OpenAI Math Release preprint OAI:One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026, 2026.
  59. [59]James Oxley. Matroid Theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, 2 edition, 2011.
  60. [60]Richard Rado. Note on independence functions. Proc. London Math. Soc. (3), 7(1):300–320, 1957.DOI
  61. [61]Aviad Rubinstein and Sahil Singla. Secretary, prophet, and stochastic probing via big-decisions-first. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC, pages 1242–1253. ACM, 2026.
  62. [62]Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. Optimal single-choice prophet inequalities from samples. In 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, pages 60:1–60:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  63. [63]Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003.
  64. [64]Sahil Singla. The Matroid Secretary Conjecture is True, 2026. arXiv:2609.14555, version 2.arxiv.org/abs/2609.14555
  65. [65]José A. Soto. Matroid secretary problem in the random-assignment model. SIAM Journal on Computing, 42(1):178–211, 2013.
  66. [66]José A. Soto, Abner Turkieltaub, and Victor Verdugo. Strong algorithms for the ordinal matroid secretary problem. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 715–734, 2018. Journal version: Mathematics of Operations Research 46(2):642–673, 2021; doi:10.1287/moor.2020.1083.
  67. [67]John von Neumann. Zur Theorie der Gesellschaftsspiele. Math. Ann., 100:295–320, 1928.DOI

Paper details

vlnc:W_yngy365c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

GPT Astra, GPT-5.6 Sol (bare), ChatGPT, Claude

View statement
Looking for related papers…
Contents