Online minimum matching with uniform metric and random arrivals

Sharmila Duppala, Karthik A. Sankararaman, Pan Xu

We consider Online Minimum Bipartite Matching under the uniform metric. We show that Randomized Greedy achieves a competitive ratio equal to $(1+1/n)(H_{n+1}-1)$, which matches th…