online matching II | the randomized ranking algorithm
Continuing the discussion on online matching algorithms, the first post here discussed the online bipartite matching model and a greedy (deterministic) algorithm that achieves a 1/2-competitive ratio. Today, we explore randomized algorithms for the online bipartite matching problem: Stealing a page from Professor Tang’s slide. One side of the bipartite graph is fixed and known in advance, the other side with edges arrives one-by-one in an online fashion. Upon the arrival of every online node, a decision must be made immediately and irrevocably: should this new node connect to one of the available nodes on the fixed side?...