Edge-weighted Online Stochastic Matching: Beating $1-\frac{1}{e}$

Shuyi Yan

We study the edge-weighted online stochastic matching problem. Since Feldman, Mehta, Mirrokni, and Muthukrishnan proposed the $(1-\frac{1}{e})$-competitive Suggested Matching algorithm…