×

A general stochastic matching model on multigraphs. (English) Zbl 1472.05123

Summary: We extend the general stochastic matching model on graphs introduced in J. Mairesse and P. Moyal [J. Appl. Probab. 53, No. 4, 1064–1077 (2016; Zbl 1356.60147)], to matching models on multigraphs, that is, graphs with self-loops. The evolution of the model can be described by a discrete time Markov chain whose positive recurrence is investigated. Necessary and sufficient stability conditions are provided, together with the explicit form of the stationary probability in the case where the matching policy is ‘First Come, First Matched’.

MSC:

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

Citations:

Zbl 1356.60147
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Adan, I., Bušić, A., Mairesse, J., and Weiss, G. Reversibility and further properties of FCFS infinite bipartite matching. Math. Oper. Res., 43 (2), 598-621 (2018a). MR3801108. · Zbl 1433.60080
[2] Adan, I., Kleiner, I., Righter, R., and Weiss, G. FCFS parallel service systems and matching models. Performance Evaluation, 127-128, 253-272 (2018b). DOI: 10.1016/j.peva.2018.10.005. · doi:10.1016/j.peva.2018.10.005
[3] Adan, I. and Weiss, G. Exact FCFS matching rates for two infinite multitype sequences. Oper. Res., 60 (2), 475-489 (2012). MR2935072. · Zbl 1298.60089
[4] Adan, I. and Weiss, G. A skill based parallel service system under FCFS-ALIS-steady state, overloads, and abandonments. Stoch. Syst., 4 (1), 250-299 (2014). MR3353219. · Zbl 1305.60091
[5] Boxma, O. J., David, I., Perry, D., and Stadje, W. A new look at organ transplantation models and double matching queues. Probab. Engrg. Inform. Sci., 25 (2), 135-155 (2011). MR2786745. · Zbl 1213.90085
[6] Brémaud, P. Markov chains. Gibbs fields, Monte Carlo simulation and queues, volume 31 of Texts in Applied Mathematics. Springer, Cham, second edition (2020). ISBN 978-3-030-45981-9; 978-3-030-45982-6. MR4174390. · Zbl 1435.60003
[7] Büke, B. and Chen, H. Stabilizing policies for probabilistic matching systems. Queueing Syst., 80 (1-2), 35-69 (2015). MR3341682. · Zbl 1319.60173
[8] Büke, B. and Chen, H. Fluid and diffusion approximations of probabilistic matching systems. Queueing Syst., 86 (1-2), 1-33 (2017). MR3642009. · Zbl 1373.60151
[9] Bušić, A., Gupta, V., and Mairesse, J. Stability of the bipartite matching model. Adv. in Appl. Probab., 45 (2), 351-378 (2013). MR3102455. · Zbl 1274.60228
[10] Caldentey, R., Kaplan, E. H., and Weiss, G. FCFS infinite bipartite matching of servers and customers. Adv. in Appl. Probab., 41 (3), 695-730 (2009). MR2571314. · Zbl 1247.90099
[11] Gurvich, I. and Ward, A. On the dynamic control of matching queues. Stoch. Syst., 4 (2), 479-523 (2014). MR3353225. · Zbl 1327.60177
[12] Jonckheere, M., Moyal, P., Ramírez, C., and Soprano-Loto, N. Generalized max-weight policies in stochastic matching. ArXiv Mathematics e-prints (2020). arXiv: 2011.0453.
[13] Mairesse, J. and Moyal, P. Stability of the stochastic matching model. J. Appl. Probab., 53 (4), 1064-1077 (2016). MR3581242. · Zbl 1356.60147
[14] Moyal, P., Bušić, A., and Mairesse, J. Loynes construction for the extended bipartite matching. ArXiv Mathematics e-prints (2018). arXiv: 1803.02788.
[15] Moyal, P., Bušić, A., and Mairesse, J. A product form for the general stochastic matching model. Journal of Applied Probability, 58 (2), 449-468 (2021). DOI: 10.1017/jpr.2020.100. · Zbl 1476.60121 · doi:10.1017/jpr.2020.100
[16] Moyal, P. and Perry, O. On the instability of matching queues. Ann. Appl. Probab., 27 (6), 3385-3434 (2017). MR3737928. · Zbl 1382.60119
[17] Nazari, M. and Stolyar, A. L. Reward maximization in general dynamic matching systems. Queueing Syst., 91 (1-2), 143-170 (2019). MR3911245. · Zbl 1437.60070
[18] Rahmé, Y. and Moyal, P. A stochastic matching model on hypergraphs. ArXiv Mathematics e-prints (2019). arXiv: 1907.12711.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.