Preprint
Sep 2026
Degree-Parameterized Analysis of Sampling-Based Online Matching
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...
Pan Xu
· 0 citations