Stability of the bipartite matching model

Details Stability of the bipartite matching model Stability of the bipartite matching model

2010-03-17

arxiv.org/abs/1003.3477v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Stability of the bipartite matching model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stability of the bipartite matching model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability of the bipartite matching model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-699679