Online Stochastic Matching: Beating 1-1/e 2: The Suggested Matching Algorithm Achieves 1 − 1/e with High Probability, and This Is Tight Even in ExpectationResearch Paper
Online bipartite matching models decisions that must be made as requests arrive: an advertiser can be assigned to a compatible request once, and an assignment cannot be revised when later requests reveal a better alternative. Display advertising is the motivating example in Feldman, Mehta, Mirrokni, and Muthukrishnan's 2009 preprint: an ad server knows…