A stochastic matching model on hypergraphs

DOI10.1017/APR.2021.8zbMATH Open1479.05244OpenAlexW3215471813MaRDI QIDQ5013243FDOQ5013243

Authors: Youssef Rahme, Pascal Moyal 

Publication date: 29 November 2021

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: Motivated by applications to a wide range of assemble-to-order systems, operations scheduling, healthcare systems and collaborative economy applications, we introduce a stochastic matching model on hypergraphs, extending the model in [15] to the case of hypergraphical (rather than graphical) matching structures. We address a discrete-event system under a random input of single items, simply using the system as an interface to be matched by groups of two or more. We study the stability of this stochastic system, for various hypergraph geometries.

Full work available at URL: https://arxiv.org/abs/1907.12711

Recommendations

• A general stochastic matching model on multigraphs
• Stochastic matching on uniformly sparse graphs
• On matchings in stochastic Kronecker graphs
• On matchings in hypergraphs
• The stochastic stability of decentralized matching on a graph
• The matching process and independent process in random regular graphs and hypergraphs
• Almost perfect matchings in random uniform hypergraphs
• On a hypergraph matching problem
• Matchings and flows in hypergraphs
• Greedy matching in bipartite random graphs

zbMATH Keywords

matchingstabilityMarkovian queueing theory

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• A condition for matchability in hypergraphs
• A new look at organ transplantation models and double matching queues
• A product form for the general stochastic matching model
• Dynamic matching for real-time ride sharing
• Exact FCFS matching rates for two infinite multitype sequences
• Fcfs infinite bipartite matching of servers and customers
• Fluid Models for Overloaded Multiclass Many-Server Queueing Systems with First-Come, First-Served Routing
• Fluid and diffusion approximations of probabilistic matching systems
• Markov Chains
• On the dynamic control of matching queues
• On the instability of matching queues
• Reversibility and further properties of FCFS infinite bipartite matching
• Reward maximization in general dynamic matching systems
• Stability of the bipartite matching model
• Stability of the stochastic matching model
• Stabilizing policies for probabilistic matching systems
• Topics in the Constructive Theory of Countable Markov Chains

Cited In (10)

• Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
• A product form for the general stochastic matching model
• Multi-component matching queues in heavy traffic
• Stability regions of systems with compatibilities and ubiquitous measures on graphs
• Stability of the stochastic matching model
• Emergence and dynamics of short food supply chains
• On the sub-additivity of stochastic matching
• A general stochastic matching model on multigraphs
• Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
• A natural barrier in random greedy hypergraph matching

This page was built for publication: A stochastic matching model on hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013243)