Papers for

kidney exchange planners

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Stochastic matching achieves near optimal size with low degree selection

Stochastic Matching with Polynomial Degree

Abstract: We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.

Mon 2 NovData Structures and Algorithms
The gist
This paper studies a problem where you have a network of connections, but each connection might work or not with some chance. The goal is to choose a smaller set of connections ahead of time so that even after some fail, you still keep most of the best possible matches, while ensuring no node has too many connections. The authors prove that it is always possible to do this with a surprisingly low maximum number of connections per node, solving a recent open question. Their proof uses a new way of rearranging matchings to make the problem easier to control.
Open → 2611.03367v1