Metraipolis › archive › dc_ca56f8d5276d

Stochastic Matching with Polynomial Degree — arXiv:2611.03367

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03367
License (as archived)
CC0-1.0
Archived
2026-11-03T18:59:03.273Z
SHA-256 of the archived text
21f9efe29d35a7f1e2dc29b8e01b5514b1d441da9389b75413c2963b539f8645
Stable URL of this page
https://metraipolis.com/documento/dc_ca56f8d5276d

How to cite

Stochastic Matching with Polynomial Degree — arXiv:2611.03367 — arXiv (en), https://arxiv.org/abs/2611.03367 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ca56f8d5276d (Metraipolis archive dc_ca56f8d5276d, sha256 21f9efe29d35a7f1e2dc29b8e01b5514b1d441da9389b75413c2963b539f8645)
BibTeX
@misc{dcca56f8d5276d,
  title = {Stochastic Matching with Polynomial Degree — arXiv:2611.03367},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03367},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ca56f8d5276d; sha256 21f9efe29d35a7f1e2dc29b8e01b5514b1d441da9389b75413c2963b539f8645},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03367. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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-\epsilon)$ 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-\epsilon)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/\epsilon)}{\epsilon^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{\epsilon p})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/\epsilon)\log(1/\epsilon))}$ 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.03367 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:18:07.752Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).