# Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation

arXiv: https://arxiv.org/abs/2602.04989 · HTML: https://mlsanity.com/paper/2602.04989/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 34 references that are in the map.
- First posted on arXiv 4 Feb 2026.

## Builds on (most cited first, 3 of 3)

- [Online Stochastic Matching: New Algorithms and Bounds](https://mlsanity.com/paper/1606.06395/) (2016)
- [Policy Optimization for Dynamic Heart Transplant Allocation](https://mlsanity.com/paper/2512.12497/) (2025)
- [Online Matching: A Brief Survey](https://mlsanity.com/paper/2407.05381/) (2024)

## Built on by (most cited first, 4 of 4)

- [Learning Potentials for Dynamic Matching and Application to Heart Transplantation](https://mlsanity.com/paper/2602.08878/) (2026)
- [Aligning Data-Driven Predictors with Allocation: A Decision-Focused Approach to Survival Analysis](https://mlsanity.com/paper/2606.02671/) (2026)
- [Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values](https://mlsanity.com/paper/2608.28620/) (2026)
- [Efficient Learning of Survival Analysis Models Under Outcome-Dependent Truncation and Censoring](https://mlsanity.com/paper/2610.12538/) (2026)

## Abstract (arXiv)

Online matching has been a mainstay in domains such as Internet advertising and organ allocation, but practical algorithms often lack strong theoretical guarantees. We take an important step toward addressing this by developing new online matching algorithms based on a coarsening approach. Although coarsening typically implies a loss of granularity, we show that, to the contrary, aggregating offline nodes into capacitated clusters can yield near-optimal theoretical guarantees. We apply our methodology to heart transplant allocation to develop theoretically grounded policies based on structural properties of historical data. Furthermore, in simulations based on real data, our policy closely matches the performance of the omniscient benchmark, achieving competitive ratio 0.91, drastically higher than the US status quo policy's 0.51. Our work bridges the gap between data-driven heuristics and pessimistic theoretical lower bounds.