Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sampling and multilevel coarsening algorithms for fast matrix approximations
This paper addresses matrix approximation problems for matrices that are large, sparse and/or that are representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsen…
Dimensionality ReductionRethinking Efficient Graph Coarsening via a Non-Selfishness Principle
Graph coarsening is a graph dimensionality reduction technique that aims to construct a smaller and more tractable graph while preserving the essential structural and semantic properties of the original graph. However, m…
Dimensionality ReductionEnhanced coarsening of charge density waves induced by electron correlation: Machine-learning enabled large-scale dynamical simulations
The phase ordering kinetics of emergent orders in correlated electron systems is a fundamental topic in non-equilibrium physics, yet it remains largely unexplored. The intricate interplay between quasiparticles and emerg…
Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transport
Hierarchical abstractions are a methodology for solving large-scale graph problems in various disciplines. Coarsening is one such approach: it generates a pyramid of graphs whereby the one in the next level is a structur…
Graph ClassificationGBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing
The objective of graph coarsening is to generate smaller, more manageable graphs while preserving key information of the original graph. Previous work were mainly based on the perspective of spectrum-preserving, using so…