Let $G=(V, E)$ be a given edge-weighted graph and let its {em realization} $mathcal{G}$ be a random subgraph of $G$ that includes each edge $e in E$ independently with probability $p$. In the {em stochastic matching} problem, the goal is to pick a sparse subgraph $Q$ of $G$ without knowing the realization $mathcal{G}$, such that the maximum weight matching among the realized edges of $Q$ (i.e. graph $Q cap mathcal{G}$) in expectation approximates the maximum weight matching of the whole realization $mathcal{G}$. In this paper, we prove that for any desirably small $epsilon in (0, 1)$, every graph $G$ has a subgraph $Q$ that guarantees a $(1-epsilon)$-approximation and has maximum degree only $O_{epsilon, p}(1)$. That is, the maximum degree of $Q$ depends only on $epsilon$ and $p$ (both of which are known to be necessary) and not for example on the number of nodes in $G$, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA18; Behnezhad et al., SODA19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC20], and essentially settles the approximation factor.
Download