Online bipartite matching with random arrivals

• DOI: 10.1145/1993636.1993716
• Publication Date: 2011-06-06T11:53:52Z
• Authors: Mohammad Mahdian; Qiqi Yan
• Keywords: Competitive Analysis; Online algorithm

In a seminal paper, Karp, Vazirani, and Vazirani show that simple ranking algorithm achieves competitive ratio of 1-1/e for the online bipartite matching problem in standard adversarial model, where is also shown to be optimal. Their result implies random arrivals model defined by Goel Mehta, nodes arrive order, greedy 1-1/e. this we study it has at least 0.696, beating ≈ 0.632 barrier model. Our extends i.i.d. distribution Feldman et al., removing assumption known.