Metraipolis › archive › dc_e28af7d68c85
Degree-Parameterized Analysis of Sampling-Based Online Matching — arXiv:2609.14486
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14486
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T23:48:45.455Z
- SHA-256 of the archived text
13db9984ed58afb984e691a240c06f7531a6a72b1baa26f259e11da875696e9f- Stable URL of this page
https://metraipolis.com/documento/dc_e28af7d68c85
How to cite
Degree-Parameterized Analysis of Sampling-Based Online Matching — arXiv:2609.14486 — arXiv (en), https://arxiv.org/abs/2609.14486 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e28af7d68c85 (Metraipolis archive dc_e28af7d68c85, sha256 13db9984ed58afb984e691a240c06f7531a6a72b1baa26f259e11da875696e9f)
BibTeX
@misc{dce28af7d68c85,
title = {Degree-Parameterized Analysis of Sampling-Based Online Matching — arXiv:2609.14486},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14486},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e28af7d68c85; sha256 13db9984ed58afb984e691a240c06f7531a6a72b1baa26f259e11da875696e9f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14486. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $\theta$. We analyze two sampling-based frameworks. For \emph{Deterministic Greedy Sampling}, which computes prices from a fixed-size initial sample and then applies a local threshold rule, we derive an explicit worst-case competitive ratio and prove it tight within this policy family for every fixed $d\ge2$ and $\theta\in[0,1]$. The optimal sampling choice interpolates between no sampling for $d=1,2$ and a dense-limit guarantee of approximately $0.2562$, improving on the classical $1/8$ analysis while retaining linear per-arrival time. We also derive worst-case bounds on the variance of the number of matched offline agents, including order-tight behavior as $\theta\to1_-$ and an $O(\theta)$ bound as $\theta\to0_+$ for fixed $m,d$. For \emph{Black-Box Sampling--Matching}, we introduce prefix-dependent reweighting followed by an arbitrary approximate offline matching solver and prove a transfer theorem whose guarantee is the offline approximation ratio times an explicit function of $d$ and $\theta$. With exact matching, the framework recovers the classical $1/e$ guarantee in the unbounded-degree limit.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-15 in cs.GT).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.14486 — 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-10-15T23:17:52.853Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).