Stability of the bipartite matching model
From MaRDI portal
Publication:2837751
Abstract: We consider the bipartite matching model of customers and servers introduced by Caldentey, Kaplan, and Weiss (Adv. Appl. Probab., 2009). Customers and servers play symmetrical roles. There is a finite set C resp. S, of customer, resp. server, classes. Time is discrete and at each time step, one customer and one server arrive in the system according to a joint probability measure on CxS, independently of the past. Also, at each time step, pairs of matched customer and server, if they exist, depart from the system. Authorized matchings are given by a fixed bipartite graph. A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete time Markov chain. We study its stability under various admissible matching policies including: ML (Match the Longest), MS (Match the Shortest), FIFO (match the oldest), priorities. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and priority policies, we exhibit a bipartite graph with a non-maximal stability region.
Recommendations
Cites work
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- A product form solution to a system with multi-type jobs and multi-type servers
- Exact FCFS matching rates for two infinite multitype sequences
- Fcfs infinite bipartite matching of servers and customers
- Markov Chains
- Non-negative matrices and Markov chains. 2nd ed
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Cited in
(21)- Stability regions of systems with compatibilities and ubiquitous measures on graphs
- Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
- Performance paradox of dynamic matching models under greedy policies
- On the sub-additivity of stochastic matching
- A stochastic matching model on hypergraphs
- Fluid and diffusion approximations of probabilistic matching systems
- Reward maximization in general dynamic matching systems
- A general stochastic matching model on multigraphs
- Heavy traffic analysis of multi-class bipartite queueing systems under FCFS
- Equivalences between two matching models: stability
- A fluid model for one-sided bipartite matching queues with match-dependent rewards
- Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
- On the optimal design of a bipartite matching queueing system
- A product form for the general stochastic matching model
- Stability of the stochastic matching model
- Stochastic non-bipartite matching models and order-independent loss queues
- Ergodic control of bipartite matching queues with class change and matching failure
- Stabilizing policies for probabilistic matching systems
- On spatial matchings: the first-in-first-match case
- Reversibility and further properties of FCFS infinite bipartite matching
- On the instability of matching queues
This page was built for publication: Stability of the bipartite matching model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2837751)
