betaFeedback

Reading v1View latest version

WorksComputer Science

Prophet Secretary for Matroids and XOS Valuations: A Strict Separation at 1−1/e1-1/e

Abstract

The matroid prophet-secretary problem asks an online algorithm to select an independent set of elements whose nonnegative values are drawn independently and revealed in uniformly random order. Its combinatorial-auction counterpart asks the algorithm to allocate disjoint bundles to arriving buyers with independently drawn XOS valuation functions. In both problems the distributions are known, and the benchmark is the expected offline optimum. Ehsani, Hajiaghayi, Kesselheim, and Singla (SODA 2018) give (1−1/e)(1-1/e)-competitive algorithms for both settings. In this work we show that these two guarantees have different limits. For every matroid, we give a randomized (1−1/e+ε0)(1-1/e+\varepsilon_0)-competitive algorithm, where ε0=10−6\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(N4)O(N^4) such queries in expectation and O(N4log⁡(N+2))O(N^4\log(N+2)) in the worst case, where NN is the number of elements. For combinatorial auctions with XOS valuations, however, we show that 1−1/e1-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/e1-1/e, even when the buyers' valuations are independent and identically distributed, every additive clause has coefficients in {0,1}\{0,1\}, and computation is unrestricted. Thus the matroid improvement exploits structure absent from general allocation with XOS valuations.

Introduction

Optimal stopping theory has long informed the design of online auctions. Hajiaghayi, Kleinberg, and Parkes [21] initiated the connection between secretary problems and online auction design, and Hajiaghayi, Kleinberg, and Sandholm [22] introduced prophet inequalities as a tool for designing and analyzing online auction mechanisms.1 These connections led to a broad study of how distributional information and random arrival can improve online allocation.

In a prophet inequality problem, the values are drawn independently from known distributions, and an online algorithm makes irrevocable decisions as they are revealed. Its performance is compared with a prophet who sees all realizations before choosing an optimal feasible solution. The arrival order may be adversarial. In a secretary problem, the values are fixed and unknown, but the arrival order is uniformly random. The prophet-secretary model [14] combines the distributional information of prophet inequalities with the random arrival order of secretary problems. The distributions are known in advance, and the arrival order is uniform and independent of the realized values.

The central difficulty is to use this information while preserving feasibility for future arrivals. Accepting a valuable element may prevent the selection of later elements, and allocating an item to one buyer makes it unavailable to every later buyer. Distributional information allows an algorithm to estimate these opportunity costs; random arrival also limits how often an early decision can block a more valuable later one. We study how the interaction between these two sources of information depends on the feasibility structure. Our two settings are matroid selection and combinatorial auctions with XOS valuations, defined next.

Problem definitions

Matroid prophet secretary. A matroid M=(E,I)M = (E,\mathcal{I}) consists of a finite ground set EE and a nonempty family I⊆2E\mathcal{I} \subseteq2^E of independent sets. The family is hereditary: every subset of a set in I\mathcal{I} also belongs to I\mathcal{I}. It satisfies the augmentation axiom: if I,J∈II,J \in\mathcal{I} and ∣I∣<∣J∣|I| < |J|, there is an element e∈J∖Ie \in J \setminus I with I∪{e}∈II \cup\{e\} \in\mathcal{I}. A basis is an inclusionwise maximal independent set; all bases have the same size, called the rank of the matroid. For nonnegative weights, the greedy algorithm scans elements in decreasing weight order and adds an element whenever independence is preserved. A fixed label order breaks ties and specifies a canonical maximum-weight basis.

The matroid and its N=∣E∣N = |E| labeled elements are known in advance. Each element ee has a nonnegative value XeX_e drawn independently from a known distribution. The elements arrive in a uniformly random order, independent of the values. At an arrival the algorithm observes the element’s label and value and must accept or reject it immediately and irrevocably. The accepted set must remain independent. Its reward is the sum of the accepted values, and the expected offline benchmark is

F0=E[max⁡I∈I∑e∈IXe].F_0 = \mathbb{E}\left[\max_{I \in\mathcal{I}} \sum_{e \in I} X_e\right].

A matroid independence oracle answers whether a queried subset S⊆ES \subseteq E belongs to I\mathcal{I}; queries may involve elements that have not arrived. For the computational result, each distribution is given explicitly as a finite list of rational values and rational probabilities. Oracle calls are counted separately from arithmetic operations and random bits. Prophet secretary for combinatorial auctions. There is a fixed item set UU and a known set of buyers. Each buyer ii has a valuation vi:2U→R≥0v_i:2^U \to\mathbb{R}_{\ge0} drawn independently from a known distribution. Buyers arrive in uniformly random order, independently of their valuations. When buyer ii arrives, the algorithm observes viv_i and irrevocably assigns her a bundle SiS_i of previously unallocated items. The objective is social welfare, ∑ivi(Si)\sum_i v_i(S_i). The offline optimum OPT maximizes this sum over all pairwise disjoint bundles after seeing every valuation.

A valuation is XOS if it is the maximum of finitely many nonnegative additive functions:

v(S)=max⁡ℓ∈L∑j∈Swℓ,j,wℓ,j≥0.v(S)=\max_{\ell\in\mathcal{L}}\sum_{j\in S}w_{\ell,j},\qquad w_{\ell,j}\ge0.

The functions indexed by ℓ∈L\ell\in\mathcal{L} are its additive clauses. A clause attaining the maximum on SS is a supporting clause for SS. Such valuations are normalized, meaning v(∅)=0v(\varnothing)=0, and monotone, meaning v(S)≤v(T)v(S)\le v(T) whenever S⊆TS\subseteq T. Independence is required across buyers’ valuation functions, not across the values that one function assigns to different bundles.

Competitive ratio. In either model, write ALG for the realized reward or welfare. We call an algorithm α\alpha-competitive, for α∈[0,1]\alpha\in[0,1], if E[ALG]≥αE[OPT]\mathbb{E}[\mathrm{ALG}]\ge\alpha\mathbb{E}[\mathrm{OPT}] on every instance with finite expected optimum. In the matroid model, E[OPT]=F0\mathbb{E}[\mathrm{OPT}]=F_0. The expectation is over the input values or valuations, the arrival order, and the algorithm’s randomness. Thus larger competitive ratios are better.

Our results

Ehsani, Hajiaghayi, Kesselheim, and Singla [12] established the same competitive ratio, 1−1/e1-1/e, for both models. Their analysis explains this guarantee through time-dependent thresholds and an exponential bound on the loss of available value. It leaves a natural question: does the common guarantee reflect the inherent difficulty of both problems?

The single-choice case already admits a better competitive ratio. Azar, Chiplunkar, and Kaplan [3] surpassed 1−1/e1-1/e, and subsequent work obtained further improvements [8, 7]. For a general matroid, however, the algorithm must account for the interactions among many accepted elements. Our main result uses the matroid exchange structure to obtain a strict improvement for every matroid.

Theorem 1 (Matroid prophet secretary). For ε0=1.01⋅10−6\varepsilon_0=1.01\cdot10^{-6}, every matroid on NN elements with independent nonnegative values and finite F0F_0 admits a randomized online algorithm satisfying

E[ALG]≥(1−1e+ε0)F0.\mathbb{E}[\mathrm{ALG}]\ge\left(1-\frac{1}{e}+\varepsilon_0\right)F_0.

For explicitly given finite distributions with rational values and probabilities and access to a matroid independence oracle, the expected number of matroid independence queries is O(N4)O(N^4) and the worst-case number is O(N4log⁡(N+2))O(N^4\log(N+2)). Its arithmetic work and number of random bits are polynomial in NN and the total binary encoding length of the distributions on every execution.

The theorem applies to arbitrary matroids. Its guarantee has no dependence on rank, on the number of possible values, or on their numerical range. The computational statement uses the full explicit input length; it is not a claim about access only to a sampling oracle. The existence guarantee for general distributions follows by approximation. We keep all algorithmic parameters symbolic until § 15, where an explicit rational choice is verified with positive slack in every required inequality.

For combinatorial auctions with XOS valuations, the same improvement is impossible. Our second result gives a matching upper bound on the competitive ratio, even when the buyers’ valuation functions are drawn independently from one common finite distribution.

Theorem 2 (Sharpness for combinatorial auctions with XOS valuations). For every ξ>0\xi> 0, there is a finite prophet-secretary instance with XOS valuations on which every randomized online algorithm satisfies

E[ALG]<(1−1e+ξ)E[OPT].\mathbb{E}[\mathrm{ALG}] < \left(1-\frac{1}{e}+\xi\right)\mathbb{E}[\mathrm{OPT}].

The buyers’ valuations may be drawn independently from the same finitely supported distribution, and every additive clause may have coefficients in {0,1}\{0,1\}. The conclusion holds even if all clauses and the entire arrival permutation are given in advance and computation is unrestricted.

Together with [12], this identifies 1−1/e1 - 1/e as the optimal competitive ratio for prophet secretary with XOS valuations. The same upper bound follows from Udwani and Wajc’s result for online welfare maximization with coverage valuations under independent and identically distributed (i.i.d.) item arrivals from a known distribution [29]. In that problem, each arriving item is assigned to one of a fixed set of buyers, whose value is the total weight of the objects covered by her assigned items, with each object counted once. A transformation that exchanges the roles of arriving items and buyers yields our model; it is related to the coverage-to-XOS construction of Chawla and Dang [6]. We state this implication explicitly and give a direct proof. The obstruction is informational: an online allocation commits to a supporting additive clause before the later types determine which clauses fit together. Offline approximation hardness alone would not imply this statement.

Our Approach and Techniques

To see why matroid prophet secretary and prophet secretary with XOS valuations separate at 1−1/e1 - 1/e, recall the unified (1−1/e)(1 - 1/e) analysis of Ehsani, Hajiaghayi, Kesselheim, and Singla [12]. The (1−1/e)(1 - 1/e) guarantee in random-order prophet models suggests two complementary paradigms: posted thresholds, which extract enough surplus above each element’s replacement cost to offset the offline value lost by accepting it, and online contention-resolution schemes, which select a feasible subset of random candidates as they arrive. Our continuation uses additional random rejections of early candidates to maintain a uniform bound on the rate at which any reference-optimum element is blocked. This gives exponential survival until a short final interval, where the algorithm removes these rejections to exploit stable overlap.

Pushing either paradigm past 1−1/e1 - 1/e on a matroid runs into two opposite regimes. In a volatile regime, rare, high-value realizations make the surplus lost by deleting an element unstable across independent draws. The baseline survival analysis gives only 1−1/e1 - 1/e. A threshold rule can nevertheless gain surplus from elements that clear their deterministic prices even when they do not belong to the offline optimal basis. These additional contributions matter because the rule processes only the next arrival: its expected surplus is the average of the individual elements’ expected surpluses, so these elements need not be simultaneously feasible. We choose the reference distribution so that this surplus covers the expected decrease in the residual benchmark, with the slack needed for a strict improvement.

In a persistent regime, a core of reliable elements repeatedly enters the offline optimal basis B(X)B(X) across independent draws (here X=(Xe)e∈EX = (X_e)_{e \in E}, a basis is a maximal independent set, and B(y)B(y) denotes the maximum-weight basis for weights yy, with a fixed label order breaking ties); here collisions between persistent winners make it useful to exploit the substantial overlap between independent optimal bases through an adaptive contention-resolution scheme near the end of the horizon. Our matroid algorithm (Theorem 1) turns this tension into a step-by-step win-win dichotomy, whereas our XOS lower bound (Theorem 2) shows that general combinatorial auctions with XOS valuations can force an early commitment to incompatible global completions.

Part I: Beating 1−1/e1 - 1/e for Matroid Prophet Secretary (Theorem 1)

As elements of an NN-element matroid arrive in random order, each outer threshold step contracts the matroid when accepting an element ee (M/eM/e) and deletes it when rejecting it (M∖eM \setminus e). Deletion forbids using ee; contraction declares I⊆E∖{e}I \subseteq E \setminus\{e\} independent exactly when I∪{e}I \cup\{e\} was independent before the contraction. Loops, elements belonging to no independent set, are discarded.

The matroid obtained by these contractions and deletions is the residual minor. In a residual minor M=(E,I)M = (E,\mathcal{I}) of size n=∣E∣≤Nn = \lvert E\rvert\leq N with a reference product distribution Y=(Ye)e∈EY = (Y_e)_{e\in E}, meaning that its coordinates are independent, write OPT⁡(M,y)=max⁡I∈I∑f∈Iyf\operatorname{OPT}(M,y) = \max_{I\in\mathcal{I}} \sum_{f\in I} y_f and let Y−eY_{-e} omit coordinate ee.

Each element ee has an exclusion threshold τe(Y−e)=OPT⁡(M∖e,Y)−OPT⁡(M/e,Y)\tau_e(Y_{-e}) = \operatorname{OPT}(M \setminus e,Y) - \operatorname{OPT}(M/e,Y)—the critical weight for ee to enter the greedy basis B(Y)B(Y), with equality resolved by the fixed tie order—so deleting ee reduces the offline optimum by OPT⁡(M,Y)−OPT⁡(M∖e,Y)=(Ye−τe)+\operatorname{OPT}(M,Y) - \operatorname{OPT}(M \setminus e,Y) = (Y_e - \tau_e)^+, where u+=max⁡{u,0}u^+ = \max\{u,0\}.

Summing de=E[(Ye−τe)+]d_e = \mathbb{E}[(Y_e - \tau_e)^+] over e∈Ee \in E gives the deletion surplus D=∑edeD = \sum_e d_e, which plays a dual role: rejecting a uniformly random next arrival drops the offline benchmark E[OPT⁡(M,Y)]\mathbb{E}[\operatorname{OPT}(M,Y)] by D/nD/n, while DD also measures the total surplus above replacement costs.

To test whether this surplus comes from rare spikes or persistent winners, we track its stable part H=∑eE[(min⁡{Ye,Ye′}−τe)+]H = \sum_e \mathbb{E}[(\min\{Y_e,Y'_e\} - \tau_e)^+] for a copy Ye′Y'_e independent of all coordinates of YY, keeping the same other-coordinate threshold τe\tau_e, which measures how much of DD survives when each element’s weight is drawn twice independently. Even when HH is tiny under the true distribution XX, however, this alone does not guarantee that the surplus of a one-step threshold rule covers the benchmark loss D/nD/n.

At each residual minor MM with positive expected optimum, we choose a nearby reference distribution under which the threshold rule can be compared with the loss in the offline benchmark. Zero-value states terminate. The reference distributions are YqY^q, for q∈J=[1−4δ,1+4δ]q \in\mathcal{J} = [1 - 4\delta, 1 + 4\delta], where δ\delta also specifies the length of the final window of the continuation. Their coordinates are independent and satisfy

peq(z)=Pr⁡[Yeq>z]=min⁡{1,qPr⁡[Xe>z]},z≥0.p_e^q(z) = \Pr[Y_e^q > z] = \min\{1, q\Pr[X_e > z]\}, \qquad z \geq0.

Thus Y1Y^1 is the original distribution. For q<1q < 1, the same distribution is obtained by independently replacing each value by zero with probability 1−q1 - q. For q>1q > 1, every upper-tail probability is increased by the factor qq until it reaches one. In particular, the occurrence probability of an unsaturated high-value event changes proportionally with qq.

Write Fq=Fq(M)F_q = F_q(M), where Fq(M′)=E[OPT⁡(M′,Yq)]F_q(M') = \mathbb{E}[\operatorname{OPT}(M',Y^q)] for a minor M′M', using the reference values on its remaining labels. As qq increases, the expected optimum is nondecreasing, while competition between elements for inclusion in an optimal basis can increase. The useful feature of this rescaling is that the marginal change in FqF_q is closely related to the expected value lost when an element is deleted. We make this relation precise below. It allows us to choose a reference parameter for which the threshold surplus and the decrease in the benchmark can be compared quantitatively.

For a fixed reference parameter qq, we write

deq=E[(Yeq−τe(Y−eq))+],Dq=∑e∈Edeq,Hq=∑e∈EE[(min⁡{Yeq,Yeq′}−τe(Y−eq))+].\begin{aligned} d_e^q &= \mathbb{E}\left[\left(Y_e^q-\tau_e(Y_{-e}^q)\right)^+\right], & D_q &= \sum_{e\in E} d_e^q,\\ H_q &= \sum_{e\in E}\mathbb{E}\left[\left(\min\{Y_e^q,Y_e^{q'}\}-\tau_e(Y_{-e}^q)\right)^+\right]. \end{aligned}

where Yeq′Y_e^{q'} is an independent copy of YeqY_e^q, independent also of Y−eqY_{-e}^q. Thus deqd_e^q is the expected loss from deleting ee under the reference distribution, and DqD_q is the sum of these losses. The quantity HqH_q measures the part of this surplus that remains when the same element must exceed the same exclusion threshold in two independent draws. These are the reference-distribution versions of the quantities defined above.

The reference search must preserve the benchmark promised by the preceding step of the algorithm. For this purpose, we use the potential

g(q)=a(q)Fq,a(q)=1−θq,g(q)=a(q)F_q,\qquad a(q)=1-\theta q,

where θ\theta is a fixed constant slightly below 1/e1/e. At q=1q=1, the reference distribution is the original one, and g(1)=(1−θ)F1g(1)=(1-\theta)F_1. We choose θ\theta so that this exceeds the target (1−1/e+ϵ0)F1(1-1/e+\epsilon_0)F_1 by enough to pay for estimation and implementation errors. At a later residual state, the search starts from the inherited reference parameter and uses its estimates to certify nondecreasing potential. These certificates are valid whenever the estimates are accurate.

As qq increases, FqF_q is nondecreasing and the coefficient a(q)a(q) is decreasing. The search uses this tradeoff to find a reference distribution suitable for one of our two algorithmic steps. To explain the resulting condition, suppose first that qq is a differentiable interior stationary point. Then

References

  1. [1][ABH+26] Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Zhiyyi Huang, Danny Mittal, and Sahil Singla. As Easy as Rank One: Optimal algorithms for matroid secretary and single-sample matroid prophet. Manuscript, October 25, 2026.
  2. [2][ABHM26] Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal. On the strong Matroid Secretary Conjecture and beyond. arXiv preprint arXiv:2609.19118, 2026.arxiv.org/abs/2609.19118
  3. [3][ACK18] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1 − 1/e barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), pages 303–318. ACM, 2018.arxiv.org/abs/1711.01834
  4. [4][AKW14] Pablo D. 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.
  5. [5][BIK07] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434–443. SIAM, 2007.DOI
  6. [6][CD26] Shuchi Chawla and Trung Dang. Single-sample prophet inequalities: A combinatorial to single-item reduction. arXiv preprint arXiv:2610.03660, 2026.arxiv.org/abs/2610.03660
  7. [7]Ziyun Chen, Zhiyi Huang, Dongchen Li, and Zhihao Gavin Tang. Prophet secretary and matching: The significance of the largest item. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1371–1401. SIAM, 2025.
  8. [8]José Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Mathematical Programming, 190:483–521, 2021.
  9. [9]Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Mathematics of Operations Research, 35(1):1–13, 2010.
  10. [10]Shaddin Dughmi, Tim Roughgarden, and Qiqi Yan. From convex optimization to randomized mechanisms: Toward optimal combinatorial auctions. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), pages 149–158. ACM, 2011.arxiv.org/abs/1103.0040
  11. [11]Shaddin Dughmi. From contention resolution to matroid secretary and back. SIAM Journal on Computing, 54(3):585–624, 2025.DOI
  12. [12]Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 700–714. SIAM, 2018.
  13. [13]Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. SIAM Journal on Computing, 53(6):1641–1662, 2024.
  14. [14]Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary. In Algorithms – ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 496–508. Springer, 2015.
  15. [15]Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 39(1):122–142, 2009.
  16. [16]Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 123–135. SIAM, 2015.
  17. [17]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. Full version: arXiv:2406.12799.arxiv.org/abs/2406.12799
  18. [18]Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1189–1201. SIAM, 2015.
  19. [19]Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1014–1033. SIAM, 2016.
  20. [20]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
  21. [21]MohammadTaghi Hajiaghayi, Robert Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, EC ’04, pages 71–80. ACM, 2004.DOI
  22. [22]MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, pages 58–65. AAAI Press, 2007.
  23. [23]Zhiyi Huang. Settling the matroid secretary problem. arXiv:2609.30421, 2026.arxiv.org/abs/2609.30421
  24. [24]Adam Kohlhaas. Sandholm receives SIGecom test of time award. Carnegie Mellon University, School of Computer Science, June 2026.
  25. [25]Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC), pages 123–136. ACM, 2012.
  26. [26]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. IEEE, 2014.arxiv.org/abs/1403.7343
  27. [27]Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics, pages 57:1–57:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.arxiv.org/abs/1806.09251
  28. [28]Sahil Singla. The matroid secretary conjecture is true. arXiv:2609.14555, 2026.arxiv.org/abs/2609.14555
  29. [29]Rajan Udwani and David Wajc. Online submodular welfare maximization: Computation is not the bottleneck. arXiv preprint arXiv:2610.16060, 2026. In FOCS 2026; arXiv version.arxiv.org/abs/2610.16060

Paper details

vlnc:W_mswuv6ng
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 22

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI Astra, Gemini Argon

View statement
Looking for related papers…
Contents