A stochastic matching model on hypergraphs

DOI10.1017/APR.2021.8zbMATH Open1479.05244arXiv1907.12711OpenAlexW3215471813MaRDI 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?)
• Markov Chains
• Topics in the Constructive Theory of Countable Markov Chains
• Title not available (Why is that?)
• A new look at organ transplantation models and double matching queues
• Stability of the stochastic matching model
• Exact FCFS matching rates for two infinite multitype sequences
• A condition for matchability in hypergraphs
• Fcfs infinite bipartite matching of servers and customers
• Reversibility and Further Properties of FCFS Infinite Bipartite Matching
• On the instability of matching queues
• Stability of the bipartite matching model
• Fluid Models for Overloaded Multiclass Many-Server Queueing Systems with First-Come, First-Served Routing
• Dynamic Matching for Real-Time Ride Sharing
• A product form for the general stochastic matching model
• Stabilizing policies for probabilistic matching systems
• Fluid and diffusion approximations of probabilistic matching systems
• Reward maximization in general dynamic matching systems

Cited In (6)

• Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
• Multi-component matching queues in heavy traffic
• Stability regions of systems with compatibilities and ubiquitous measures on graphs
• On the sub-additivity of stochastic matching
• 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)