Premium
Randomized greedy matching
Author(s) -
Dyer Martin,
Frieze Alan
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020104
Subject(s) - greedy algorithm , combinatorics , matching (statistics) , mathematics , randomized algorithm , upper and lower bounds , enhanced data rates for gsm evolution , graph , greedy randomized adaptive search procedure , discrete mathematics , algorithm , computer science , statistics , artificial intelligence , mathematical analysis
We consider a randomized version of the greedy algorithm for finding a large matching in a graph. We assume that the next edge is always randomly chosen from those remaining. We analyze the performance of this algorithm when the input graph is fixed. We show that there are graphs for which this Randomized Greedy Algorithm (RGA) usually only obtains a matching close in size to that guaranteed by worst‐case analysis (i.e., half the size of the maximum). For some classes of sparse graphs (e.g., planar graphs and forests) we show that the RGA performs significantly better than the worst‐case. Our main theorem concerns forests. We prove that the ratio to maximum here is at least 0.7690…, and that this bound is tight.