Online Stochastic Matchings: Stability on Hypergraphs

Fabien Mathieu (NPA)

Online Stochastic Matchings: Stability on Hypergraphs

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read The paper proves that a stochastic matching system on a hypergraph is stabilizable exactly when the arrival-rate vector lies in the interior of the cone generated by the hyperedge columns, and that a single rate-blind policy stabilizes ever

desk verdict A genuine extension of the graph stabilization characterization to hypergraphs, with a constructive maximally stable policy; the main theorem looks right, though the sufficiency proof is intricate and not machine-checked. read the letter →

arxiv 2607.18935 v2 pith:PY2Z34WG submitted 2026-07-21 cs.NI

Fabien Mathieu (NPA) This is my paper · ORCID

classification cs.NI MSC 60K2505C6590B22

keywords stochasticdynamicmatchinghypergraphsstabilizabilityconservationconevirtualqueuepositiverecurrenceMaxWeightmaximallystablepolicy

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

A matching system with finitely many item classes is stabilizable if and only if the arrival rates can be written as a nonnegative combination of hyperedge columns with the active columns spanning all classes. The paper proves this for arbitrary hyperedges, including hyperedges that consume several items of a class and hyperedges that discard a single class, and it holds without any 'general position' assumption on the rates. Sufficiency is achieved by one fixed policy, Virtual-Queue Match-the-Longest, which ignores the arrival rates entirely; the same policy works for every stabilizable instance, so it is maximally stable. The proof rests on a signed virtual queue whose positive recurrence — the key technical step that earlier work cited without proving — is established here. On hypergraphs this is a real difference from graphs: greedy policies can fail, and idling is sometimes necessary, so the existence of a single universal stabilizing rule is not obvious.

What carries the argument

The central object is the conservation cone cone(A) = {Aμ : μ≥0} generated by the hyperedge incidence columns, together with the signed virtual queue Q(t) ∈ Z^n updated by a MaxWeight rule over multisets of at most two hyperedges per arrival, with an idle clause that makes the nonpositive orthant a 'parking area.' The key identity is the pathwise slaving lemma Q(t)=U(t)−D(t) with U(t)⋅D(t)=0, so unassigned physical items equal the positive part of the virtual queue and residual demand equals its negative part; consequently the physical system regenerates exactly when the virtual queue hits zero. A budget of two hyperedges per epoch is what makes a uniform inward drift possible (Lemma 5.2), a

What would settle it

For the candy hypergraph of the paper, take λ=(1.5,1,1.1,1,1.1,1,1.5): this vector lies outside the cone (the unique solution of Aμ=λ has negative entries), so Theorem 3.1 predicts that no admissible policy — even one allowed to idle and use arbitrary countable internal state — can make the queue process positive recurrent; exhibiting any such policy would refute the necessity direction. Conversely, for the stable family λα=(1,1,3α,α,3α,1,1) with α=0.2, running VQML in simulation should show the mean central queue Q4 staying bounded; an observed linear growth would refute the sufficiency proof

Watch

Extended reading notes

Core claim

Theorem 3.1: For a hypergraph matching problem (G,λ) with positive arrival rates, the following are equivalent: (i) the problem is stabilizable; (ii) no nonzero vector y satisfies ⟨y,A_k⟩≥0 for every hyperedge k and ⟨y,λ⟩≤0 (no 'boundary certificate'); (iii) the conservation equation Aμ=λ admits a strictly positive solution and A has full row rank, i.e. λ lies in the interior of the cone generated by the hyperedge columns; (iv) the conservation equation admits a nonnegative solution whose support induces a surjective submatrix. Moreover, VQML, a rewardless variant of the Extended Greedy Primal–Dual policy, defined from the incidence matrix alone, stabilizes every instance satisfying these co

Load-bearing premise

The entire characterization depends on the model assumption that items are removed only by controller-chosen hyperedge activations — spontaneous or exogenous departures are not allowed — because VQML's proof of stability uses a pathwise slaving between the physical queues and a signed virtual queue that forced removals would break.

Editorial extensions

If this is right

Stabilizability of any hypergraph matching problem is decidable by linear algebra alone: check whether λ lies in the interior of cone(A), or find a nonnegative solution of Aμ=λ with surjective support; no simulation or search over policies is needed.
A single, rate-blind policy (VQML) is maximally stable across all hypergraph matching instances, so the same controller works without knowing arrival rates or tuning parameters.
The criterion covers controlled discards (mono-edges): adding a discard edge for a class can only enlarge the cone, so partial controlled discarding is handled by the same theorem, and full discarding makes every instance trivially stabilizable.
For simple graphs the cone condition recovers the classical independent-set inequalities and non-bipartiteness, so the hypergraph result is a strict generalization of the known characterization.
Idling is provably necessary on hypergraphs: the 'candy' example shows every greedy (non-idling) policy fails for some stabilizable instance, while VQML with its idle clause succeeds.

Reading between the lines

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

Since VQML is rate-oblivious, it would likely remain stabilizing in slowly time-varying environments as long as the instantaneous rates stay strictly inside the cone; the paper does not analyze this, but the uniform construction makes it a natural testable conjecture.
The cone condition offers a fast diagnostic for deployed systems: certifying stabilizability reduces to a linear feasibility program, so a system designer can check before deployment whether any matching policy can keep queues finite.
The sharp boundary of the result is the absence of spontaneous departures: the paper's Remark 4.2 suggests that exogenous abandonment can break VQML's slaving and even destabilize otherwise stabilizable instances, so a matching theorem under abandonment would need new machinery.
The support-surjectivity form (iv) has a practical advantage: it makes no global assumption on A, so stabilizability can be checked by searching for any nonnegative conservation solution whose active columns span the class space, which may be cheaper than testing all columns.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Here is my read. The paper does what it says: it takes the cone/support characterization that [6] had for simple graphs, extends it to hypergraphs with multiplicities and mono-edges, and proves that a single lambda-oblivious policy (VQML) stabilizes every stabilizable instance. The necessity direction is clean: stationarity plus CLT gives exact balance and kills boundary certificates. The sufficiency proof is the real work—signed virtual queue drift, steering lemma, pathwise slaving, renewal transfer—and I did not find a step that has to be false. The tie-breaking issue in Remark 5.3 is genuine and the idle clause handles it; the candy example has a derived instability threshold, not a fitted one.

Worth giving credit for the second contribution: Nazari and Stolyar asserted positive recurrence of the signed chain; this paper proves it. That matters because the property is not automatic. The disclosure of the concurrent Nguyen–Bušić paper is complete, and the extra coverage (multiplicities, mono-edges, signed-queue proof) is real. The companion notebook reproduces the candy simulations and the adversarial tie-breaking search, which helps.

Soft spots, in proportion. The theorem is explicitly scoped to controlled activations. Spontaneous departures are excluded, and Remark 4.2 says outright that forced removals break the pathwise slaving and would require a new maximally stable witness. That is an honest boundary, not a hidden flaw. The sufficiency chain is intricate and the appendix arguments are not machine-checked; my confidence is moderate, not high. If I were editing, I would send it to a referee with queueing expertise and ask them to verify Lemma 5.4's steering construction and Lemma 5.6's renewal-transfer step. The overlap with [20] is not a problem—both are derived independently, and this one covers more.

For whom: people working on stochastic matching, multi-way queues, and stabilizability. It settles a question that was open. I would bring it to a reading group and would cite it. Verdict: it deserves a serious referee; likely accept after the proof check.

Referee Report

0 major / 4 minor

Summary. The paper studies stochastic dynamic matching on hypergraphs, where items of finitely many classes arrive by independent Poisson processes and are removed in multisets when hyperedges are activated. Theorem 3.1 characterizes stabilizability of (G,λ) by four equivalent conditions, centered on the existence of a nonnegative solution Aμ=λ whose support induces a surjective submatrix, equivalently λ∈int cone(A), equivalently the absence of a boundary certificate. Necessity is proved by a stationarity-plus-CLT argument (Proposition 5.1) that does not rely on the policy structure beyond exogenous arrivals and bounded increments. Sufficiency is constructive: the paper introduces Virtual-Queue Match-the-Longest (VQML), a λ-oblivious signed-queue MaxWeight policy with an idle clause, and proves it stabilizes every stabilizable instance. The proof supplies a uniform inward drift for the signed virtual queue, a steering/accessibility lemma for the origin, pathwise slaving of the physical system to the virtual queue, and a regeneration transfer to the physical chain. A candy hypergraph example shows that greedy (non-idling) policies can be unstable on stabilizable instances, so idling is necessary on hypergraphs. The model is explicitly restricted to controlled activations; spontaneous/exogenous departures are outside the scope and are flagged as future work.

Significance. The result is significant: it extends the known graph characterization to arbitrary hypergraphs with multiplicities and mono-edges, removes general-position assumptions, and provides a single λ-oblivious maximally stable policy. The necessity direction is elegant and robust, and the sufficiency chain is intricate but coherent. I specifically checked the paper's claim that it supplies the previously asserted-but-unproved positive recurrence of the signed virtual queue: Lemma 5.3 gives the uniform drift, Lemma 5.4 gives accessibility of the origin, and Proposition 5.2 assembles them via Foster's criterion, including the subtle tie-breaking pitfall documented in Remark 5.3. The pathwise slaving identities (Lemma 5.5) and the transfer argument (Lemma 5.6) are consistent and cover the non-irreducible signed chain. The concurrent-work note and the candy simulation notebook are useful. The stress-test concern about circularity does not land: both theorem directions are genuinely derived, and the scope limitation to controlled activations is explicit rather than hidden. I found no load-bearing flaw.

minor comments (4)

[Lemma 5.3] The inequality chain after the definition of D is compressed: max over the integer feasible set is bounded below by max over the real polytope D only because the maximum of a linear objective over D occurs at a vertex, and all vertices {0,2e_k} lie in the integer feasible set. This is correct, but as written it can look like a direction error. Please spell out that reasoning in one sentence.
[Remark 5.5] The claim that at most three matchings complete per epoch is unnecessarily loose. Since only one item arrives per epoch, at most one existing backlog entry can be filled by the arrival, and at most one appended entry can be filled by the same item. The actual bound is at most two; the looser bound is harmless for assumption (b), but the accompanying sentence about both appended entries completing is misleading.
[Remark 4.2 / Abstract] The exclusion of spontaneous departures is clearly stated in Remark 4.2, but the abstract and title could make the scope more prominent, e.g. by saying 'controlled activations' or 'without exogenous departures' in the first sentence. This would prevent readers from expecting the result to cover abandonment models.
[Equation (3)] The 'lexicographically smallest maximizer' tie-break depends on a fixed ordering of hyperedges, which is only implicit. Please state that an arbitrary but fixed ordering of E is chosen once and for all; otherwise the policy is not fully specified.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: both directions of Theorem 3.1 are genuinely derived; VQML's stabilizing property is proven here, not imported from [6]/[19].

full rationale

I find no circular reduction. The necessity direction (Proposition 5.1) argues from an arbitrary stabilizing policy using only stationarity of the queue process and bounded increments: it derives exact balance lambda-bar = A mu-bar, then excludes boundary certificates via a tightness-versus-CLT contradiction; the cone condition is never assumed. The sufficiency direction is constructive: condition (iii) enters only as the hypothesis of Lemma 5.2 (open-map argument) and Lemma 5.3 (drift), while accessibility of the origin is a separate deterministic steering construction (Lemma 5.4) that does not use the cone condition, and positive recurrence of the signed virtual queue is proven via Foster's criterion (Proposition 5.2) rather than imported. The paper explicitly says of Nazari-Stolyar [19] that 'for the signed chain... we could locate no proof,' and supplying it is a stated contribution. The transfer to the physical system rests on pathwise identities proven by induction over the epoch pipeline (Lemma 5.5, Corollary 5.1) and a renewal-reward argument (Lemma 5.6); Remark B.1 states 'We re-prove rather than import them' regarding the [19] bounds. The only self-citation of any relevance is [6] (shared author), cited as the 'starting point of the present paper,' but Lemma 5.1 re-proves the needed convex duality self-containedly (closed cone, open map, separating hyperplane), so the citation is contextual, not load-bearing. Model scope boundaries (no exogenous departures; decisions at arrival epochs; controlled activations only) are stated explicitly in Remarks 3.1 and 4.2, where the paper candidly leaves genuine spontaneous departures to future work; this is an honest limitation, not a hidden assumption that does the theorem's work. The empirical Figure 2 is illustrative simulation and does not feed back into any derivation step. The score of 1 reflects only the acknowledged self-citation anchoring ([6]) and the paper's own transparent identification of the gap in prior work, not any circular step.

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

The theorem introduces no free parameters: λ and A are inputs, and the policy's budget-2/idle-clause choices are design decisions proven sufficient, not quantities fitted to data. The axioms are standard probabilistic/geometric tools plus two model-scoping assumptions that the author flags explicitly (Remarks 3.1 and 4.2).

assumptions (7)

standard math Foster–Lyapunov criterion for irreducible countable Markov chains; positive recurrence from negative drift outside a finite set.
Used in Lemma 5.3 and Proposition 5.2 to establish positive recurrence of the signed virtual queue; taken as textbook background [3].
standard math Classical central limit theorem for i.i.d., zero-mean, finite-variance increments.
Prop 5.1 Step 2 needs S_t non-tight while X is stationary; CLT is the contradiction engine.
standard math Renewal–reward theorem and Kac's formula for stationary Markov chains.
Lemma 5.6 turns regeneration cycles into long-run activation rates and identifies the stationary mean μ̄.
standard math Closedness of finitely generated convex cones and hyperplane separation.
Lemma 5.1 proves (ii)⇔(iii); separation of λ from cone(A) is the only geometric input.
domain assumption Arrivals are independent Poisson streams per class with i.i.d. class marks and all λ_i>0.
Section 3 model; positivity of every λ_i is used in the necessity CLT step (σ²>0) and in the steering reachability bound (λ̄_min>0).
domain assumption Admissible policy class: countable Markov state, decisions at arrival epochs only, uniformly bounded activations per epoch; stabilizability is relative to this class.
Section 3, Remark 3.1; the author proves the equivalence over this class and notes it strictly extends [6, App. A]; stabilizability over broader policy classes is not treated.
domain assumption No spontaneous/exogenous departures; removals occur only via policy-activated hyperedges (mono-edges model controlled discards).
Remark 4.2; forced removals break Lemma 5.5 pathwise slaving, so the characterization and VQML do not extend to abandonment/expiry models, which the author leaves to future work.

invented entities (1)

Virtual-Queue Match-the-Longest (VQML) with signed virtual queue Q∈Z^n and budget-2 MaxWeight rule plus idle clause
purpose: Single λ-oblivious policy that stabilizes every hypergraph matching problem with λ∈int cone(A); the proof requires Q's positive recurrence and the pathwise slaving of the physical backlog to Q.
An algorithmic device inside the paper's proof, not a physical entity; its only 'evidence' is the theorem proof and companion simulations, so it carries no falsifiable handle outside the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Online Stochastic Matchings: Stability on Hypergraphs." pith.science (2026). https://pith.science/paper/PY2Z34WG

@misc{pith2026260718935,
  author       = {Pith},
  title        = {Pith review of: Online Stochastic Matchings: Stability on Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PY2Z34WG}},
  note         = {Machine review of arXiv:2607.18935}
}

abstract

We study stochastic dynamic matching on hypergraphs: items of finitely many classes arrive over time and are removed in multisets by activating hyperedges. We characterize stabilizability, the existence of a matching policy under which the queue process is positive recurrent, in terms of the arrival rates and the incidence matrix alone: (G, $\lambda$) is stabilizable if and only if the conservation equation A$\mu$ = $\lambda$ admits a nonnegative solution whose support induces a surjective submatrix, equivalently $\lambda$ lies in the interior of the cone generated by the hyperedges. This extends a characterization known for simple graphs (non-bipartiteness together with the independent-set inequalities) to arbitrary hyperedges, allowing multiplicities and mono-edges, and, unlike the constant-regret theory, needs no general-position assumption. Sufficiency is constructive: a single $\lambda$-oblivious policy, Virtual-Queue Match-the-Longest (VQML), a rewardless variant of the Extended Greedy Primal-Dual policy of Nazari and Stolyar, stabilizes every stabilizable instance and is therefore maximally stable. The sufficiency proof requires the positive recurrence of the signed virtual queue underlying VQML; previous analyses invoke this property but, to our knowledge, do not prove it, and supplying it is a second contribution.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 13 canonical work pages

[6]

Online Stochastic Matching: A Polytope Perspective

C \'e line Comte, Fabien Mathieu, Sushil Mahavir Varma, and Ana Bu s i \'c . Online Stochastic Matching: A Polytope Perspective . Working paper (HAL version 6), November 2025. URL: https://hal.science/hal-03502084v6

2025
[20]

Stability in stochastic hypergraph matching I: necessary and sufficient criteria

Doan Dai Nguyen and Ana Bu s i \'c . Stability in stochastic hypergraph matching I : necessary and sufficient criteria, 2026. arXiv preprint, posted July 26, 2026. https://doi.org/10.48550/arXiv.2607.23778 doi:10.48550/arXiv.2607.23778

work page Pith review arXiv doi:10.48550/arxiv.2607.23778 2026
[1]

Stability regions of systems with compatibilities and ubiquitous measures on graphs

Jocelyn Begeot, Irène Marcovici, and Pascal Moyal. Stability regions of systems with compatibilities and ubiquitous measures on graphs. Queueing Systems , 103(3):275--312, 2023. https://doi.org/10.1007/s11134-023-09872-0 doi:10.1007/s11134-023-09872-0

work page doi:10.1007/s11134-023-09872-0 2023
[2]

A general stochastic matching model on multigraphs

Jocelyn Begeot, Irène Marcovici, Pascal Moyal, and Youssef Rahme. A general stochastic matching model on multigraphs. ALEA, Lat. Am. J. Probab. Math. Stat. , 18(2):1325--1351, 2021. https://doi.org/10.30757/ALEA.v18-49 doi:10.30757/ALEA.v18-49

work page doi:10.30757/alea.v18-49 2021
[3]

Markov Chains : Gibbs Fields , Monte Carlo Simulation , and Queues

Pierre Br \'e maud. Markov Chains : Gibbs Fields , Monte Carlo Simulation , and Queues . Texts in Applied Mathematics . Springer-Verlag, New York, 1999. https://doi.org/10.1007/978-1-4757-3124-8 doi:10.1007/978-1-4757-3124-8

work page doi:10.1007/978-1-4757-3124-8 1999
[4]

Stability of the bipartite matching model

Ana Bušić, Varun Gupta, and Jean Mairesse. Stability of the bipartite matching model. Advances in Applied Probability , 45(2):351--378, June 2013. https://doi.org/10.1239/aap/1370870122 doi:10.1239/aap/1370870122

arXiv 2013
[5]

Kaplan, and Gideon Weiss

René Caldentey, Edward H. Kaplan, and Gideon Weiss. FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability , 41(3):695--730, 2009. https://doi.org/10.1239/aap/1253281061 doi:10.1239/aap/1253281061

arXiv 2009
[7]

Stochastic non-bipartite matching models and order-independent loss queues

Céline Comte. Stochastic non-bipartite matching models and order-independent loss queues. Stochastic Models , 38(1):1--36, January 2022. https://doi.org/10.1080/15326349.2021.1962352 doi:10.1080/15326349.2021.1962352

arXiv 2022

Show all 26 references

[8]

Greedy algorithm for multiway matching with bounded regret

Varun Gupta. Greedy algorithm for multiway matching with bounded regret. Operations Research , 72(3):1139--1155, 2024. https://doi.org/10.1287/opre.2022.2400 doi:10.1287/opre.2022.2400

2024
[9]

On the dynamic control of matching queues

Itai Gurvich and Amy Ward. On the dynamic control of matching queues. Stochastic Systems , 4(2):479--523, 2014. https://doi.org/10.1287/13-SSY097 doi:10.1287/13-SSY097

2014 doi
[10]

Hitting-time and occupation-time bounds implied by drift analysis with applications

Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability , 14(3):502--525, 1982. https://doi.org/10.2307/1426671 doi:10.2307/1426671

1982 doi
[11]

Generalized max-weight policies in stochastic matching

Matthieu Jonckheere, Pascal Moyal, Claudia Ramírez, and Nahuel Soprano-Loto. Generalized max-weight policies in stochastic matching. Stochastic Systems , 13(1):40--58, 2023. https://doi.org/10.1287/stsy.2022.0098 doi:10.1287/stsy.2022.0098

2023
[12]

Dynamic matching: Characterizing and achieving constant regret

S \"u leyman Kerimov, Itai Ashlagi, and Itai Gurvich. Dynamic matching: Characterizing and achieving constant regret. Management Science , 70(5):2799--2822, 2024. https://doi.org/10.1287/mnsc.2021.01215 doi:10.1287/mnsc.2021.01215

2024
[13]

On the optimality of greedy policies in dynamic matching

S \"u leyman Kerimov, Itai Ashlagi, and Itai Gurvich. On the optimality of greedy policies in dynamic matching. Operations Research , 73(1):560--582, 2025. https://doi.org/10.1287/opre.2021.0596 doi:10.1287/opre.2021.0596

2025
[14]

Stability of the stochastic matching model

Jean Mairesse and Pascal Moyal. Stability of the stochastic matching model. Journal of Applied Probability , 53(4):1064--1077, 12 2016. https://doi.org/10.1017/jpr.2016.65 doi:10.1017/jpr.2016.65

2016 doi
[15]

New frontiers for stochastic matching

Jean Mairesse and Pascal Moyal. New frontiers for stochastic matching. Queueing Systems , 100(3-4):473--475, 2022. https://doi.org/10.1007/s11134-022-09832-0 doi:10.1007/s11134-022-09832-0

2022 doi
[16]

Online Stochastic Matchings: Stability on Hypergraphs -- companion notebook

Fabien Mathieu. Online Stochastic Matchings: Stability on Hypergraphs -- companion notebook . Companion page, stochastic-matching documentation, 2026. URL: https://balouf.github.io/stochastic_matching/companion/hypergraph_candy.html

2026
[17]

A product form for the general stochastic matching model

Pascal Moyal, Ana Bušić, and Jean Mairesse. A product form for the general stochastic matching model. Journal of Applied Probability , 58(2):449--468, 06 2021. https://doi.org/10.1017/jpr.2020.100 doi:10.1017/jpr.2020.100

2021 doi
[18]

On the instability of matching queues

Pascal Moyal and Ohad Perry. On the instability of matching queues. The Annals of Applied Probability , 27(6):3385--3434, 2017. https://doi.org/10.1214/17-AAP1283 doi:10.1214/17-AAP1283

2017 doi
[19]

Mohammadreza Nazari and Alexander L. Stolyar. Reward maximization in general dynamic matching systems. Queueing Systems , 91(1):143--170, February 2019. https://doi.org/10.1007/s11134-018-9593-y doi:10.1007/s11134-018-9593-y

2019 doi
[21]

A stochastic matching model on hypergraphs

Youssef Rahme and Pascal Moyal. A stochastic matching model on hypergraphs. Advances in Applied Probability , 53(4):951--980, December 2021. https://doi.org/10.1017/apr.2021.8 doi:10.1017/apr.2021.8

2021 doi
[22]

Alexander L. Stolyar. Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems , 50(4):401--457, 2005. https://doi.org/10.1007/s11134-005-1450-0 doi:10.1007/s11134-005-1450-0

2005 doi
[23]

Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control , 37(12):1936--1948, 1992. https://doi.org/10.1109/9.182479 doi:10....

1936 doi
[24]

A throughput optimal scheduling policy for a quantum switch

Thirupathaiah Vasantam and Don Towsley. A throughput optimal scheduling policy for a quantum switch. In Quantum Computing, Communication, and Simulation II , volume 12015, pages 14--23, Bellingham, Washington, 2022. SPIE . https://doi.org/10.1117/12.2616950 doi:10.1117/12.2616950

2022 doi
[25]

Yehua Wei, Jiaming Xu, and Sophie H. Yu. Constant regret primal-dual policy for multi-way dynamic matching, 2023. Working paper. URL: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4357216

2023
[26]

Jhunjhunwala, and Siva Theja Maguluri

Martin Zubeldia, Prakirt R. Jhunjhunwala, and Siva Theja Maguluri. Matching queues with abandonments in quantum switches: Stability and throughput analysis. Operations Research , 74(1):339--355, 2026. https://doi.org/10.1287/opre.2023.0032 doi:10.1287/opre.2023.0032

2026

Pith tools

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

[1] [6]

Online Stochastic Matching: A Polytope Perspective

C \'e line Comte, Fabien Mathieu, Sushil Mahavir Varma, and Ana Bu s i \'c . Online Stochastic Matching: A Polytope Perspective . Working paper (HAL version 6), November 2025. URL: https://hal.science/hal-03502084v6

2025

[2] [20]

Stability in stochastic hypergraph matching I: necessary and sufficient criteria

Doan Dai Nguyen and Ana Bu s i \'c . Stability in stochastic hypergraph matching I : necessary and sufficient criteria, 2026. arXiv preprint, posted July 26, 2026. https://doi.org/10.48550/arXiv.2607.23778 doi:10.48550/arXiv.2607.23778

work page Pith review arXiv doi:10.48550/arxiv.2607.23778 2026

[3] [1]

Stability regions of systems with compatibilities and ubiquitous measures on graphs

Jocelyn Begeot, Irène Marcovici, and Pascal Moyal. Stability regions of systems with compatibilities and ubiquitous measures on graphs. Queueing Systems , 103(3):275--312, 2023. https://doi.org/10.1007/s11134-023-09872-0 doi:10.1007/s11134-023-09872-0

work page doi:10.1007/s11134-023-09872-0 2023

[4] [2]

A general stochastic matching model on multigraphs

Jocelyn Begeot, Irène Marcovici, Pascal Moyal, and Youssef Rahme. A general stochastic matching model on multigraphs. ALEA, Lat. Am. J. Probab. Math. Stat. , 18(2):1325--1351, 2021. https://doi.org/10.30757/ALEA.v18-49 doi:10.30757/ALEA.v18-49

work page doi:10.30757/alea.v18-49 2021

[5] [3]

Markov Chains : Gibbs Fields , Monte Carlo Simulation , and Queues

Pierre Br \'e maud. Markov Chains : Gibbs Fields , Monte Carlo Simulation , and Queues . Texts in Applied Mathematics . Springer-Verlag, New York, 1999. https://doi.org/10.1007/978-1-4757-3124-8 doi:10.1007/978-1-4757-3124-8

work page doi:10.1007/978-1-4757-3124-8 1999

[6] [4]

Stability of the bipartite matching model

Ana Bušić, Varun Gupta, and Jean Mairesse. Stability of the bipartite matching model. Advances in Applied Probability , 45(2):351--378, June 2013. https://doi.org/10.1239/aap/1370870122 doi:10.1239/aap/1370870122

arXiv 2013

[7] [5]

Kaplan, and Gideon Weiss

René Caldentey, Edward H. Kaplan, and Gideon Weiss. FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability , 41(3):695--730, 2009. https://doi.org/10.1239/aap/1253281061 doi:10.1239/aap/1253281061

arXiv 2009

[8] [7]

Stochastic non-bipartite matching models and order-independent loss queues

Céline Comte. Stochastic non-bipartite matching models and order-independent loss queues. Stochastic Models , 38(1):1--36, January 2022. https://doi.org/10.1080/15326349.2021.1962352 doi:10.1080/15326349.2021.1962352

arXiv 2022