| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429033 | Information Processing Letters | 2011 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marek Adamczyk,