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 threshold rule, we derive an explicit worst-case competitive ratio and prove it tight within this policy family for every fixed $d\ge 2$ 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\mathrm{/}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 \to 1_{-}$ and an $O(\theta )$ bound as $\theta \to 0_{+}$ 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\mathrm{/}e$ guarantee in the unbounded-degree limit.