Greedy Matching in Bipartite Random Graphs

References

• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proc. Sympos. Discrete Algorithms, 1253–1264.Google Scholar
• Aronson J, Dyer M, Frieze A, Suen S (1995) Randomized greedy matching ii. Random Structures Algorithms 6(1):55–73.Google Scholar
• Besser B, Poloczek M (2017) Greedy matching: Guarantees and limitations. Algorithmica 77:201–234.Google Scholar
• Borodin A, Nielsen M, Rackoff C (2003) (incremental) priority algorithms. Algorithmica 37:295–326.Google Scholar
• Chan THH, Chen F, Wu X, Zhao Z (2018) Ranking on arbitrary graphs: Rematch via continuous lp with monotone and boundary condition constraints. SIAM J. Comput. 47(4):1529–1546.Google Scholar
• Dietzfelbinger M, Goerdt A, Mitzenmacher M, Montanari A, Pagh R, Rink M (2010) Tight thresholds for cuckoo hashing via xorsat. Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide F, Spirakis P, eds. Automata, Languages and Programming, vol. 6198 of Lecture Notes in Computer Science (Springer, Berlin), 213–225.Google Scholar
• Dyer M, Frieze A (1991) Randomized greedy matching. Random Structures Algorithms 2(1):29–45.Google Scholar
• Dyer M, Frieze A, Pittel B (1993) The average performance of the greedy matching algorithm. Annals Appl. Probability 3(2):526–552.Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci., 117–126.Google Scholar
• Fountoulakis N, Panagiotou K (2012) Sharp load thresholds for cuckoo hashing. Random Structures Algorithms 41(3):306–333.Google Scholar
• Frieze A, Melsted P, Mitzenmacher M (2011) An analysis of random-walk cuckoo hashing. J. Comput. 40(2):291–308.Google Scholar
• Frieze A, Radcliffe A, Suen S (1995) Analysis of a simple greedy matching algorithm on random cubic graphs. Combinatorics Probability Comput. 4:47–66.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms 982–991.Google Scholar
• Goel G, Tripathi P (2012) Matching with our eyes closed. Proc. Sympos. Fondations Comput. Sci. 718–727.Google Scholar
• Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. Proc. ACM Sympos. Theory Comput.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput., 352–358.Google Scholar
• Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps. Proc. 43rd Annual ACM Sympos. Theory Comput., 597–606.Google Scholar
• Mastin A, Jaillet P (2018) Greedy online bipartite matching on random graphs. https://people.llnl.gov/mastin1.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundation Trends Theoretical Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Google Scholar
• Poloczec M, Szegedy M (2012) Randomized greedy algorithms for the maximum matching problem with new analysis. Proc. 2012 IEEE 53rd Annual Sympos. Foundations Comput. Sci., 708–717.Google Scholar
• Tang ZG, Wu X, Zhang Y (2020) Toward a better understanding of randomized greedy matching. Proc. Sympos. Theory of Comput., 1097–1110.Google Scholar
• Tinhofer G (1984) A probabilistic analysis of some greedy cardinality matching algorithms. Ann. Oper. Res. 1(3):239–254.Google Scholar
• Wormald NC (1995) Differential equations for random processes and random graphs. Annals Appl. Probability 5(4):1217–1235.Google Scholar
• Wormald NC (1999) The differential equation method for random graph processes and greedy algorithms. Lectures on Approximation and Randomized Algorithms (Wydawnictwo Naukowe Pwn), 73–155.Google Scholar