Stochastic Matching with Few Queries: New Algorithms and Tools

Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi +1

We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph $G(V,E)$ along with a parameter $p\in (0,1)$ is given in the input. Each ed…