Stability of the bipartite matching model

DOI10.1239/AAP/1370870122zbMATH Open1274.60228arXiv1003.3477OpenAlexW1979318710MaRDI QIDQ2837751FDOQ2837751

Ana Bušić, Varun Gupta, Jean Mairesse

Publication date: 11 July 2013

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

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.

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

Recommendations

• Stability of the stochastic matching model
• Reversibility and further properties of FCFS infinite bipartite matching
• A product form for the general stochastic matching model
• A general stochastic matching model on multigraphs
• Fcfs infinite bipartite matching of servers and customers

zbMATH Keywords

stabilitybipartite matchingMarkovian 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) Flows in graphs (05C21)

Cites Work

• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Non-negative matrices and Markov chains. 2nd ed
• Markov Chains
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• 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

Cited In (18)

• Reward maximization in general dynamic matching systems
• Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
• A product form for the general stochastic matching model
• Heavy traffic analysis of multi-class bipartite queueing systems under FCFS
• Stability regions of systems with compatibilities and ubiquitous measures on graphs
• On the Optimal Design of a Bipartite Matching Queueing System
• A stochastic matching model on hypergraphs
• On the sub-additivity of stochastic matching
• A general stochastic matching model on multigraphs
• Reversibility and Further Properties of FCFS Infinite Bipartite Matching
• Stabilizing policies for probabilistic matching systems
• Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
• Performance paradox of dynamic matching models under greedy policies
• Fluid and diffusion approximations of probabilistic matching systems
• Stochastic non-bipartite matching models and order-independent loss queues
• On spatial matchings: The first-in-first-match case
• On the instability of matching queues
• Equivalences between two matching models: stability

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)