Greedy algorithm for stochastic matching is a 2-approximation
classification
💻 cs.DS
keywords
approximationgreedymatchingstochasticalgorithmapplicationschenconfirm
read the original abstract
Motivated by applications in online dating and kidney exchange, the stochastic matching problem was introduced by Chen, Immorlica, Karlin, Mahdian and Rudra (2009). They have proven a 4-approximation of a simple greedy strategy, but conjectured that it is in fact a 2-approximation. In this paper we confirm this hypothesis.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.