Improved analysis of the greedy algorithm for stochastic matching

The stochastic matching problem with applications in online dating and kidney exchange was introduced by Chen et al. (2009) [1] together with a simple greedy strategy. They proved it is a 4-approximation, but conjectured that the greedy algorithm is in fact a 2-approximation. In this paper we confirm this hypothesis.

► Stochastic matching problem with applications in online dating and kidney exchange.
► Tight ratio for the simple greedy algorithm.
► Improved insight based on the previous analysis.