Pith. sign in

REVIEW 2 major objections 4 minor 26 references

Stationary Online Contention Resolution Schemes

T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper introduces stationary OCRSs and shows they achieve optimal selectability constants for bipartite matchings and k-uniform matroids via explicit maximum-entropy algorithms.

desk verdict Strong, novel theory paper with a real gap in the recurring-OCRS reduction; main results stand, but Proposition 1 overclaims adaptivity. read the letter →

arxiv 2603.21532 v2 pith:ZXW6VKVH submitted 2026-03-23 cs.GT cs.DMcs.DSmath.CO

Mohammad Reza Aminian , Rad Niazadeh , Pranav Nuti This is my paper
classification cs.GTcs.DMcs.DSmath.CO MSC 90C2705C7005B3568W27
keywords stationaryonlinecontentionresolutionschemesmaximumentropyGibbsdistributionbipartitematchingsk-uniformmatroidsweaklyRayleighsimulate-then-replaceprophetinequality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper defines a class of online contention resolution schemes whose output distribution is independent of arrival order, and shows this 'stationary' restriction is exact: every stationary scheme is equivalent to a distribution satisfying two linear constraints, and every such distribution can be realized by a universal simulate-then-replace online rule. It then constructs witness distributions by maximum entropy (Gibbs) and proves they achieve a selectability of (3−√5)/2 for bipartite matchings, a Poisson-CDF constant α_k for k-uniform matroids, and 1/2 for weakly Rayleigh matroids; the bipartite and uniform-matroid constants are optimal within the stationary class. The paper argues these are not merely feasible but often simpler than known OCRSs, and that stationarity is precisely what enables the transparent algorithms. This matters because the same schemes yield improved prophet inequalities for bipartite matching and transfer to recurring/reusable-resource allocation, where arrival order is genuinely reshuffled.

What carries the argument

The key machinery is the stationary OCRS LP plus the maximum-entropy Gibbs distribution as its witness family, tied together by the simulate-then-replace meta-algorithm. In a Gibbs distribution with weights w, the conditional probability of selecting e given the entire rest of the set is either 0 or the constant ρ_e = w_e/(1+w_e); hence the stationary-implementability constraint becomes the addability lower bound P[Add(e)] ≥ α. The addability event is what varies by environment: 'both endpoints unmatched' in bipartite matchings (analysed with the monomer–dimer positive-correlation inequality), 'fewer than k elements selected' in k-uniform matroids (analysed with a Poisson comparison lemma),

What would settle it

On a small bipartite graph, compute the stationary OCRS LP optimum (or run the explicit upper-bound construction from the proof of Lemma 3) for a sequence of fractional matchings; if any stationary distribution achieves selectability above (3−√5)/2, the claimed optimum falls. Alternatively, search for positive edge weights on a bipartite graph where the partition-function inequality Z(G)Z(G−u−v) ≥ Z(G−u)Z(G−v) fails for some edge uv; such a failure would invalidate the addability calculation.

Watch

Extended reading notes

Core claim

The central discovery is that restricting OCRSs to be stationary—output set distribution identical under every arrival order—does not cost power in the environments studied; it converts the design problem into a distribution-selection problem. The stationary OCRS LP is exact: a distribution is implementable iff it satisfies selectability (marginal inclusion ≥ α x_e) and stationary implementability (conditional inclusion given all other selections ≤ x_e), and Algorithm 1 (simulate-then-replace) implements any such distribution online. For the maximum-entropy Gibbs distribution with marginals αx, stationary implementability reduces to a single addability condition—every element must be addable

Load-bearing premise

The bipartite matching result stands or falls on the positive-correlation lemma for Gibbs distributions over bipartite matchings: conditioned on all other selections, the two endpoints of an edge being unmatched must be positively correlated, because the addability calculation multiplies these two probabilities directly.

Editorial extensions

If this is right

  • The bipartite matching S-OCRS yields a prophet inequality with competitive ratio (3−√5)/2 ≈ 0.382, improving on prior matching prophet inequalities and resolving the open case of non-vanishing activation probabilities.
  • The k-uniform matroid S-OCRS achieves the optimal stationary selectability α_k ≈ 1−√(2/(πk))+O(1/k) with a simple greedy-with-random-discarding rule; its stationarity transfers directly to recurring/reusable-resource allocation, where the same factor improves the previous best bound.
  • The weakly Rayleigh matroid construction gives an explicit 1/2-selectable S-OCRS for graphic, laminar, and C-representable matroids, matching the best possible factor and providing a concrete algorithm where earlier OCRSs were implicit.
  • The exact LP characterization implies that any future feasibility environment can be tackled by searching for a distribution satisfying the two linear constraints; a simulation oracle and conditional probabilities suffice to run the resulting online policy.
  • The stationary class is not universally as strong as OCRSs: for the 2-uniform matroid the best S-OCRS has selectability 3/5 while the best OCRS exceeds 0.61, so the framework trades a small gap for structure and explicitness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The addability criterion suggests a general recipe: for any downward-closed environment, identify a correlation inequality that controls P[Add(e)] under a tilted measure; the same LP-to-policy pipeline could then produce S-OCRSs for knapsack, intersection, or scheduling constraints.
  • The permutation-invariance property can be read as a fairness certificate: in settings where agents can influence arrival times, a stationary scheme removes any advantage from timing manipulation, which could be exploited in market-design applications beyond contention resolution.
  • The simulate-then-replace template is essentially a coupling between a static distribution and the online arrival process; one testable extension is to replace the stationary conditioning S−e with other conditioning sets (e.g., random-order or prefix histories) to see whether the same distributional LP yields tight random-order OCRSs.
  • The Poisson-CDF constant α_k suggests that the selectability of the optimal stationary scheme is governed by the tail of a Poisson(k) regardless of the exact marginals; a natural test is whether the same formula appears for other feasible sets with a size-like matroid rank, such as laminar matroids with capacities.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper introduces a new class of online contention resolution schemes called stationary OCRSs (S-OCRSs), in which the distribution of the final selected set is independent of the arrival order. It gives an LP characterization of S-OCRSs and a universal simulate-then-replace implementation, then constructs explicit S-OCRSs for several feasibility environments via maximum-entropy Gibbs distributions. The main results are: a 1/3-selectable S-OCRS for general matchings (extended to a 1/(L+1)-selectable scheme for rank-L hypergraph matchings), an optimal (3−√5)/2-selectable S-OCRS for bipartite matchings, an optimal α_k-selectable S-OCRS for k-uniform matroids where α_k = P[Q < k | Q ≤ k], Q ~ Poisson(k), and a 1/2-selectable S-OCRS for weakly Rayleigh matroids. It also claims a reduction from the recurring (reusable-resource) OCRS problem to ordinary S-OCRSs, and discusses polynomial-time implementation.

Significance. If correct, this is a valuable and unifying framework. The LP characterization in Proposition 2 and the simulate-then-replace meta-algorithm are clean and constructive; the addability reduction in Section 4.2 turns online design into a static probabilistic statement. The explicit constants and the optimality results for bipartite matchings and k-uniform matroids are significant, and the bipartite matching result improves known bounds for the associated prophet inequality. The paper is also unusually explicit about implementability, including MCMC and interpolation-based sampling in the e-companion. The main caveat is that one of the motivating applications—the reduction to recurring OCRS—is overstated in its current form, and one e-companion proof of a classical correlation lemma appears invalid as written.

major comments (2)
  1. [§3.2, Proposition 1] The proof of Proposition 1 claims that the simulate-then-replace update preserves the law of the state bS under any interleaving of renewals. This is valid only when the sequence of renewed coordinates is independent of the current state. With an adaptive renewal order—where the adversary observes the current bS and chooses the next element to renew—the induction breaks. Concrete counterexample: k=1, n=2, x_1=x_2=1/2, and μ(∅)=μ({1})=μ({2})=1/3. This μ satisfies the S-OCRS LP with α=2/3. Consider the interleaving that renews element 2 when bS∈{∅,{1}} and renews element 1 when bS={2}. Starting from μ, whenever element 1 is renewed from state {2}, its acceptance probability is 0, so element 1 is never accepted at such renewals; the selectability guarantee fails. The state distribution is also not preserved. The reusable-resource application in §1.2 and the recurrence reduction rest on this
  2. [EC.1.3, Lemma 2] The proof of Lemma 2, which is load-bearing for Theorem 2, is not valid as written. The map Φ in EC.1.3 defines C_v as the component of M_u△M_v containing v and asserts that this alternating path cannot contain u because G is bipartite. This is false: u can be an internal vertex of the component. Example: take M_u = {u-v, u2-v2, u3-v3} and M_v = {u-v2, u2-v3}. Then C_v is the path v-u-v2-u2-v3-u3, which contains u as an internal vertex. With the proposed swap, the matching N contains the edge u-v2, so N ∉ M(G-u-v). The statement of Lemma 2 is a classical theorem (Heilmann–Lieb/Molloy–Reed), so the theorem can be salvaged by citing a correct source, but the paper's claim to give a self-contained proof is not supported. Please replace EC.1.3 with a correct proof or remove the completeness claim and rely on the literature.
minor comments (4)
  1. [§5.3, Theorem 4] For k=1, the theorem gives selectability 0, which is consistent but degenerate. The proof says γk is at least the median of T, which is not generally true when γ=0 and k=1. Please add a caveat that the nontrivial claim is for k≥2, or handle k=1 separately.
  2. [§1.2 / §7] The notation x∈bP is used in the abstract and Section 1.2 but the parameter b is not defined until Section 7. Define it at first use.
  3. [EC.1.1, proof of Proposition 2] In the LP⇒S-OCRS direction, the event H is described informally as 'the event that S agrees with the already-realized past selections.' This is standard but could be made precise by defining H as the cylinder set corresponding to the actual prefix decisions; otherwise the conditional probability q_e is not formally specified.
  4. [Throughout] There are several OCRS-related references listed but not discussed (e.g., Feldman et al. 2026, MacRury et al. 2025 in the introduction); this is acceptable for a broad survey-style introduction, but the related work section could be tightened to separate the papers that are actually used from those merely mentioned.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: derivations are self-contained; constants are derived, not fitted.

full rationale

The paper's chain is: (1) define S-OCRS; (2) prove equivalence to the stationary OCRS LP in both directions (Prop. 2, EC.1.1); (3) for Gibbs max-entropy solutions, reduce LP feasibility to addability (Eq. 13 and ADDABILITY); (4) prove addability in each environment with problem-specific inequalities (union bound, Heilmann–Lieb positive correlation, Poisson comparison) and prove matching upper bounds by explicit LP counterexamples (Lemmas 3 and 5, EC.1.4 and EC.1.8). No parameter is fit to the target result: alpha* solves (1−alpha)^2=alpha independently of any instance, alpha_k is a Poisson CDF ratio derived from E[Q|Q≤k]=kα_k, and 1/2 comes from Rayleigh negative correlation. The positive-correlation lemma is cited but also proved in EC.1.3; the Poisson comparison is proved in EC.1.6; the max-entropy dual is standard convex analysis. Self-citations (Aminian et al. 2026, Ma et al. 2024) appear only as motivation/context and are not used to establish the central theorems. The claimed optimality within S-OCRS is established by the paper's own upper-bound constructions, not by invoking an external uniqueness theorem. Therefore there is no self-definitional step, no fitted prediction passed off as a prediction, and no load-bearing self-citation.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The paper introduces a new algorithmic class (S-OCRS) and new definitions, but not new physical or mathematical entities with external falsifiable handles. The main free design choice is the target selectability alpha in the max-entropy program, and one explicit gamma parameter in a secondary k-uniform variant.

free parameters (1)
  • gamma (homogeneous thinning rate) = 1 − [sqrt(k/2)]/k, where [.] is nearest integer
    Chosen by hand in Theorem 4 to satisfy a median/mode inequality for the simpler greedy-with-random-discarding variant; it is not fitted to data and is not part of the optimal alpha_k result.
assumptions (6)
  • domain assumption Downward-closed feasibility family and independent Bernoulli activations with probabilities x_e.
    This is the standard OCRS setting and the base of all definitions in Section 2.
  • standard math For p = alpha*x in the relative interior of P, the maximum-entropy program has a unique solution with finite Gibbs weights (Slater's condition).
    Used in Lemma 1 and throughout Section 4 to obtain the Gibbs product form.
  • standard math Lemma 2: in a bipartite Gibbs matching measure, the events that two vertices on opposite sides are matched are positively correlated (Heilmann–Lieb / Molloy–Reed).
    This external theorem is the load-bearing input for the alpha* addability lower bound in Theorem 2.
  • standard math Ultra-log-concavity of Poisson-binomial sequences (Liggett, Pemantle) is used inside Lemma 4.
    The Poisson comparison lemma for k-uniform matroids relies on this known result.
  • domain assumption Weakly Rayleigh matroids are defined as matroids admitting a full-support Rayleigh probability measure on bases.
    This restricts Theorem 5 to a subclass of matroids; the paper proves S8 is not weakly Rayleigh but does not provide a Rayleigh base measure for all matroids.
  • domain assumption Polynomial-time implementation requires FPRAS/evaluation oracles for matchings, a DP or high-precision oracle for k-uniform matroids, and determinant oracles for C-representable matroids.
    The complexity claims in EC.2 are conditional on these oracles; they are satisfied for the named environments but not for arbitrary weakly Rayleigh matroids.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stationary Online Contention Resolution Schemes." pith.science (2026). https://pith.science/paper/ZXW6VKVH

@misc{pith2026260321532,
  author       = {Pith},
  title        = {Pith review of: Stationary Online Contention Resolution Schemes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZXW6VKVH}},
  note         = {Machine review of arXiv:2603.21532}
}
abstract

Online contention resolution schemes (OCRSs) are a central tool in Bayesian online selection and resource allocation: they convert fractional ex-ante relaxations into feasible online policies while preserving each marginal probability up to a constant factor. Despite their importance, designing (near) optimal OCRSs is often technically challenging, and many existing constructions rely on indirect reductions to prophet inequalities and LP duality, resulting in algorithms that are difficult to interpret or implement. In this paper, we introduce "stationary online contention resolution schemes (S-OCRSs)," a permutation-invariant class of OCRSs in which the distribution of the selected feasible set is independent of arrival order. We show that S-OCRSs admit an exact distributional characterization together with a universal online implementation. We then develop a general `maximum-entropy' approach to construct and analyze S-OCRSs, reducing the design of online policies to constructing suitable distributions over feasible sets. This yields a new technical framework for designing simple and possibly improved OCRSs. We demonstrate the power of this framework across several canonical feasibility environments. In particular, we obtain an improved $(3-\sqrt{5})/2$-selectable OCRS for bipartite matchings, attaining the independence benchmark conjectured to be optimal and yielding the best known prophet inequality for this setting. We also obtain a $1-\sqrt{2/(\pi k)} + O(1/k)$-selectable OCRS for $k$-uniform matroids and a simple, explicit $1/2$-selectable OCRS for weakly Rayleigh matroids (including all $\mathbb{C}$-representable matroids such as graphic and laminar). While these guarantees match the best known bounds, our framework also yields concrete and systematic constructions, providing transparent algorithms in settings where previous OCRSs were implicit or technically involved.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

26 extracted references · 2 linked inside Pith

  1. [1]

    Hence, forℓ= 0,

    At an optimum, all constraints (EC.17) must be tight: if for someℓthe inequality is strict, then shifting e-companion toAminian, Niazadeh, Nuti:Stationary Online Contention Resolution Schemesec11 an infinitesimal mass fromπ ℓ toπ ℓ+1 increasesE[|S|]and preserves feasibility for sufficiently small shifts. Hence, forℓ= 0, . . . , k−1, πℓ+1 πℓ = q 1−q · n−ℓ ...

    2010

  2. [2]

    Thus, once the constants{ρ e}and an initial sample bS∼µ ∗ are available, each arrival can be processed in polynomial time

    ec16e-companion toAminian, Niazadeh, Nuti:Stationary Online Contention Resolution Schemes The only online computations are (a) determining whetherT∪ {e} ∈ Fand (b) sampling a Bernoulli draw with parameterρ e/xe. Thus, once the constants{ρ e}and an initial sample bS∼µ ∗ are available, each arrival can be processed in polynomial time. We thus need to explai...

    2014

  3. [4]

    Proof of Theorem 4 (S-OCRS without solving concave program) Proof.Note thatP S∼µ[e∈S|S −e =T]is equal to eitherρ e or0

    Thus we must havebak ≤ bbk.□ EC.1.7. Proof of Theorem 4 (S-OCRS without solving concave program) Proof.Note thatP S∼µ[e∈S|S −e =T]is equal to eitherρ e or0. Since we have explicitly chosenρ e =γx e withγ= 1− h√ k/2 i k <1, STATIONARY-IMPLEMENTABILITYis satisfied automatically, so we concentrate on checking SELECTABILITYwithα= 1− q 2 k+1, i.e., PS∼µ[e∈S]≥ ...

    1968

  4. [5]

    Online job assignment.arXiv preprint arXiv:2506.06893,

    Farbod Ekbatani, Yiding Feng, Ian Kash, and Rad Niazadeh. Online job assignment.arXiv preprint arXiv:2506.06893,

    arXiv

  5. [7]

    Robustness of online inventory balancing to inventory shocks.arXiv preprint arXiv:2511.16044,

    Aminian, Niazadeh, Nuti:Stationary Online Contention Resolution Schemes 33 Yiding Feng, Rad Niazadeh, and Amin Saberi. Robustness of online inventory balancing to inventory shocks.arXiv preprint arXiv:2511.16044,

    arXiv

  6. [8]

    Therefore,S 8 is not weakly Rayleigh

    Moreover,S 8 is not Rayleigh; see Choe and Wagner (2006). Therefore,S 8 is not weakly Rayleigh. e-companion toAminian, Niazadeh, Nuti:Stationary Online Contention Resolution Schemesec15 EC.1.12. Proof of Lemma 6 (Dominating base point) Proof.Consider the nonempty polyhedron Q := n y∈[0,1] E : X e∈T ye ≤rank M(T)∀T⊆E,y≥x o . Letqmaximize P e∈E ye overQ. If...

    2006

  7. [12]

    Online contention resolution schemes for network revenue management and combi- natorial auctions

    Will Ma, Calum MacRury, and Jingwei Zhang. Online contention resolution schemes for network revenue management and combi- natorial auctions. In17th Innovations in Theoretical Computer Science Conference (ITCS 2026), pages 100–1. Schloss Dagstuhl– Leibniz-Zentrum f¨ur Informatik,

    2026

  8. [13]

    Concentration inequalities for log-concave sequences.International Mathematics Re- search Notices, 2026(4):rnag023,

    Arnaud Marsiglietti and James Melbourne. Concentration inequalities for log-concave sequences.International Mathematics Re- search Notices, 2026(4):rnag023,

    2026

Show all 26 references
  1. [17]

    Thereforelim sup ε→0 α≤( √ 3−1)/2, as claimed.□ EC.1.6

    = 2t0(1 +t0) 1 + 4t0 + 2t2 0 = 1 1 + √ 3 = √ 3−1 2 . Thereforelim sup ε→0 α≤( √ 3−1)/2, as claimed.□ EC.1.6. Proof of Lemma 4 (Poisson comparison) Proof.Writea t :=P[T=t]andb t :=P[Q=t], and define the corresponding truncated distributions on {0,1, . . . , k}: bat :=P[T=t|T≤k]...

    1997

  2. [20]

    Similarly, from∆ iℓh≥0, divide byw k >0and letw k →0to obtain µ(B1)µ(B3)−µ(B 2)µ(B4)≥0

    From∆ ikh≥0, divide byw ℓ >0and letw ℓ →0to obtain µ(B2)µ(B4)−µ(B 1)µ(B3)≥0. Similarly, from∆ iℓh≥0, divide byw k >0and letw k →0to obtain µ(B1)µ(B3)−µ(B 2)µ(B4)≥0. Hence µ(B1)µ(B3) =µ(B 2)µ(B4), as desired. □ The spacesV M andW M.Following Br ¨and´en and D’Le´on (2010), letV ...

    2010

  3. [21]

    LetW M ⊆V M be the subspace of functions of the form ν(B) = X e∈B ve (B∈ B) for some vector(v e)e∈E ∈R E

    = 0 for every degenerate quadrangle(B 1, B2, B3, B4)of bases ofM. LetW M ⊆V M be the subspace of functions of the form ν(B) = X e∈B ve (B∈ B) for some vector(v e)e∈E ∈R E. We have the following analog of Theorem 2.3 in Br¨and´en and D’Le´on (2010). The proof is exactly the sam...

    2010

  4. [24]

    13 In our applications we takep=αxwith a fixedα <1, which placespin the relative interior ofPand ensures that an optimal dual solution exists with finite coordinates

    Fromθwe recover the optimal weightswandρ e viaw e =e θe andρ e =w e/(1 +we). 13 In our applications we takep=αxwith a fixedα <1, which placespin the relative interior ofPand ensures that an optimal dual solution exists with finite coordinates. e-companion toAminian, Niazadeh, ...

    2014

  5. [25]

    Letµ ∗ denote an optimal solution

    := P S∈F ν(S) log ν(S)/µ 0(S) . Letµ ∗ denote an optimal solution. Whenµ0 is uniform on F, the objective differs fromH(µ)by an additive constant, so this is equivalent to the usual maximum-entropy program (MAX-ENTROPY). Forθ∈R E define the tilt ofµ 0 by µθ(S) := µ0(S) exp P e∈...

    2019

  6. [26]

    Suppose the following conditions hold: (i)Rank oracle:There is an oracle that, givenT⊆E, returns rank M(T)in polynomial time. (ii)High precision/ evaluation oracle:There is an oracle that, givenw∈R E >0 and accuracy parameter η∈(0,1/2), returns a multiplicative(1±η)-approximat...

    2003

  7. [1978]

    Optimal online contention resolution schemes via ex-ante prophet inequalities

    Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In26th Annual European Symposium on Algorithms (ESA 2018), volume 112, page

    2018

  8. [1986]

    Jiashuo Jiang, Will Ma, and Jiawei Zhang

    doi: 10.1016/0304-3975(86)90174-X. Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multiunit prophet inequalities and online stochastic knapsack.Oper- ations Research, 73(3):1703–1721, 2025a. Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tightness without counterexa...

    doi

  9. [1999]

    URLhttps://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1088.pdf. Ph.D. dissertation; Tech- nical Report No. UCB/CSD-99-1088. Nisheeth K Vishnoi.Algorithms for convex optimization. Cambridge University Press,

    1999

  10. [2006]

    Posted price mechanisms for a random stream of customers

    Jos´e Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for a random stream of customers. InProceedings of the 2017 ACM Conference on Economics and Computation, pages 169–186,

    2017

  11. [2008]

    Online advance admission scheduling for services with customer preferences

    Xinshang Wang, Van-Anh Truong, and David Bank. Online advance admission scheduling for services with customer preferences. arXiv preprint arXiv:1805.10412,

    arXiv

  12. [2010]

    New philosopher inequalities for online bayesian matching, via pivotal sampling

    Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, and David Wajc. New philosopher inequalities for online bayesian matching, via pivotal sampling. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3029–3068. SIAM,

    2025

  13. [2011]

    The e-companion (EC) starts next page

    e-companion toAminian, Niazadeh, Nuti:Stationary Online Contention Resolution Schemesec1 This page is intentionally blank. The e-companion (EC) starts next page. ec2e-companion toAminian, Niazadeh, Nuti:Stationary Online Contention Resolution Schemes EC.1. Missing Proofs and T...

    2002

  14. [2021]

    Nearly tight sample complexity for matroid online contention resolution

    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

  15. [2022]

    Asymptotically optimal competitive ratio for online allocation of reusable resources

    Vineet Goyal, Garud Iyengar, and Rajan Udwani. Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research, 73(4):1897–1915,

    1915

  16. [2024]

    Simple and optimal online contention resolution schemes for k-uniform matroids

    Atanas Dinev and S Matthew Weinberg. Simple and optimal online contention resolution schemes for k-uniform matroids. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pages 39–1. Schloss Dagstuhl–Leibniz-Zentrum f ¨ur Informatik,

    2024

  17. [2025]

    Random order vertex arrival contention resolution schemes for matching, with applications

    Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random order vertex arrival contention resolution schemes for matching, with applications. In48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 68–1. Schloss Dagstuhl–Le...

    2021

  18. [2026]

    Nearly optimal pricing algorithms for production constrained and laminar bayesian selection

    Nima Anari, Rad Niazadeh, Amin Saberi, and Ali Shameli. Nearly optimal pricing algorithms for production constrained and laminar bayesian selection. InProceedings of the 2019 ACM Conference on Economics and Computation, pages 91–92,

    2019

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.