Skip to main content
SpringerLink
Log in

Markovian Online Matching Algorithms on Large Bipartite Random Graphs

  • Published:
Methodology and Computing in Applied Probability Aims and scope Submit manuscript

A Correction to this article was published on 28 December 2022

This article has been updated

Abstract

In this paper, we present an approximation of the matching coverage on large bipartite graphs, for local online matching algorithms based on the sole knowledge of the remaining degree of the nodes of the graph at hand. This approximation is obtained by applying the Differential Equation Method to a measure-valued process representing an alternative construction, in which the matching and the graph are constructed simultaneously, by a uniform pairing leading to a realization of the bipartite Configuration Model. The latter auxiliary construction is shown to be equivalent in distribution to the original one. It allows to drastically reduce the complexity of the problem, in that the resulting matching coverage can be written as a simple function of the final value of the process, and in turn, approximated by a simple function of the solution of a system of ODE’s. By way of simulations, we illustrate the accuracy of our estimate, and then compare the performance of an algorithm based on the minimal residual degree of the nodes, to the classical greedy matching.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Data Availability

NA.

Change history

References

  • Bermolen P, Jonckheere M, Larroca F, Moyal P (2016) Estimating the transmission probability in wireless networks with configuration models. ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS) 1(2):1–23

    Article  Google Scholar 

  • Bermolen P, Jonckheere M, Moyal P (2017) The jamming constant of uniform random graphs. Stochastic Processes and their Applications 127(7):2138–2178

    Article  MathSciNet  MATH  Google Scholar 

  • Bermolen P, Jonckheere M, Larroca F, Saenz M (2019) Degree-greedy algorithms on large random graphs. ACM SIGMETRICS Performance Evaluation Review 46(3):27–32

    Article  Google Scholar 

  • Billingsley P (2013) Convergence of probability measures. John Wiley & Sons

  • Bollobás B, Béla B (2001) Random graphs. 73, Cambridge university press

  • Borodin A, MacRury C, Rakheja A (2020) Bipartite stochastic matching: Online, random order, and iid models. arXiv preprint arXiv:2004.14304

  • Brightwell G, Janson S, Luczak M (2017) The greedy independent set in a random graph with given degrees. Random Struct Algoritm 51(4):565–586

    Article  MathSciNet  MATH  Google Scholar 

  • Brualdi RA, Harary F, Miller Z (1980) Bigraphs versus digraphs via matrices. J Graph Theory 4(1):51–73

    Article  MathSciNet  MATH  Google Scholar 

  • Brubach B, Grammel N, Ma W, Srinivasan A (2021) Follow your star: New frameworks for online stochastic matching with known and unknown patience. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp 2872–2880

  • Chen J, Huang Q, Kanj I, Xia G (2021) Optimal streaming algorithms for graph matching. arXiv preprint arXiv:2102.06939

  • Chen N, Olvera-Cravioto M (2013) Directed random graphs with given degree distributions. Stochastic Systems 3(1):147–186. https://doi.org/10.1214/12-SSY076

    Article  MathSciNet  MATH  Google Scholar 

  • Decreusefond L, Moyal P (2008) Fluid limit of a heavily loaded edf queue with impatient customers. Markov Process Related Fields 14:131–157

    MathSciNet  MATH  Google Scholar 

  • Decreusefond L, Moyal P (2008) A functional central limit theorem for the M/GI/∞ queue. Ann Appl Probab 18(6):2156–2178

    Article  MathSciNet  MATH  Google Scholar 

  • Decreusefond L, Dhersin JS, Moyal P, Tran VC (2012) Large graph limit for an SIR process in random network with heterogeneous connectivity. Ann Appl Probab 22(2):541–575. https://doi.org/10.1214/11-AAP773

  • Doytchinov B, Lehoczky J, Shreve S (2001) Real-time queues in heavy traffic with earliest-deadline-first queue discipline. Ann Appl Probab 332–378

  • Edmonds J (1965) Paths, trees, and flowers. Can J Math 17:449–467. https://doi.org/10.4153/CJM-1965-045-4

  • Farhadi A, Hajiaghayi MT, Mah T, Rao A, Rossi RA (2020) Approximate maximum matching in random streams. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp 1773–1785

  • Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp 117–126

  • Gamarnik D, Goldberg DA (2010) Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections. Comb Probab Comput 19(1):61–85

    Article  MathSciNet  MATH  Google Scholar 

  • Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. SODA 8:982–991

    MathSciNet  MATH  Google Scholar 

  • Gromoll HC, Puha AL, Williams RJ (2002) The fluid limit of a heavily loaded processor sharing queue. Ann Appl Probab 12(3):797–859

    Article  MathSciNet  MATH  Google Scholar 

  • Hofstad R (2016) Random Graphs and Complex Networks, Cambridge Series in Statistical and Probabilistic Mathematics, vol 1. Cambridge University Press. https://doi.org/10.1017/9781316779422

  • Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, NY, USA, STOC ’90, p 352-358. https://doi.org/10.1145/100216.100262

  • Kaspi H, Ramanan K (2011) Law of large numbers limits for many-server queues. Ann Appl Probab 21(1):33–114

    Article  MathSciNet  MATH  Google Scholar 

  • Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, NY, USA, STOC ’11, p 597-606. https://doi.org/10.1145/1993636.1993716

  • Molloy M, Reed B, Newman M, Barabási AL, Watts DJ (2011) A critical point for random graphs with a given degree sequence. In: The Structure and Dynamics of Networks, Princeton University Press, pp 240–258

  • Newman M (2018) Networks. Oxford University Press

    Book  MATH  Google Scholar 

  • Tirodkar S (2018) Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model. In: Ganguly S, Pandya P (eds) 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), Schloss Dagstuhl–Leibniz-Zentrum fur Informatik, Dagstuhl, Germany, Leibniz International Proceedings in Informatics (LIPIcs), vol 122, pp 39:1–39:16. https://doi.org/10.4230/LIPIcs.FSTTCS.2018.39, http://drops.dagstuhl.de/opus/volltexte/2018/9938

  • Wormald NC (1999) The differential equation method for random graph processes and greedy algorithms.  Lectures on Approximation and Randomized Algorithms 73:155

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Alliance Sorbonne Universités, LMAC, Université de Technologie de Compiègne, Compiègne, France

    Mohamed Habib Aliou Diallo Aoudi & Vincent Robin

  2. IECL, Université de Lorraine and INRIA / PASTA, Nancy, France

    Pascal Moyal

Authors
  1. Mohamed Habib Aliou Diallo Aoudi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pascal Moyal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vincent Robin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pascal Moyal.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The original online version of this article was revised: The History Dates were missing in the originally published version of this article.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Aoudi, M.H.A.D., Moyal, P. & Robin, V. Markovian Online Matching Algorithms on Large Bipartite Random Graphs. Methodol Comput Appl Probab 24, 3195–3225 (2022). https://doi.org/10.1007/s11009-022-09973-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11009-022-09973-y

Keywords

Search

Navigation