论文标题
随机加权匹配：$（1-ε）$近似
Stochastic Weighted Matching: $(1-ε)$ Approximation
论文作者
论文摘要
令$ g =（v，e）$为给定的边缘加权图，然后让其{\ em实现} $ \ Mathcal {g} $是$ g $的随机子图，其中包括每个Edge $ e \ in E $ in E $ in e $ in e $ in e $ in o y $ in o $ p $ p $。在{\ em随机匹配}问题中，目标是在不知道实现$ \ nathcal {g} $的情况下选择一个稀疏的子图$ q $ q $ of $ g $，以便在实现的$ q $中的最大重量匹配（即图形$ q \ q \ cap \ cap \ cap \ nathcal {g} $）在预期的最大匹配中，该匹配的最大程度匹配的是agtimation nime的最大匹配。 $ \ MATHCAL {G} $。 在本文中，我们证明，对于任何希望的小$ε\ in（0，1）$，每个图$ g $都有一个子图$ q $，可以保证$（1-ε）$ - 近似值，并且最高度只有$ o_ {ε，p}（1）$。也就是说，$ Q $的最高度仅取决于$ε$和$ p $（这两个都是必要的），而不是在$ g $，edge-weights等中的节点数量上，等等。 随机匹配问题已在加权和未加权图上进行了广泛的研究。以前，只有（接近）半个亚图的存在以加权图[Yamaguchi和Maehara，Soda'18而闻名； Behnezhad等人，Soda'19]。我们的结果对这些作品有很大的改善，与未加权图的最新图像相匹配[Behnezhad等，Stoc'20]，并且基本上解决了近似因素。
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 $ε\in (0, 1)$, every graph $G$ has a subgraph $Q$ that guarantees a $(1-ε)$-approximation and has maximum degree only $O_{ε, p}(1)$. That is, the maximum degree of $Q$ depends only on $ε$ 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, SODA'18; Behnezhad et al., SODA'19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC'20], and essentially settles the approximation factor.
