论文标题
随机流中的最大重量B匹配
Maximum Weight b-Matchings in Random-Order Streams
论文作者
论文摘要
我们考虑在随机订单半流模型中的最大权重$ b $匹配问题。假设所有权重都是从$ [1，w] $绘制的小整数，我们使用$ o（\ max（| m_g |，n）\ cdot poly（$ log（$ dem），$ white $ white $ white $ white $ white $ y $ white $ y $ y $ white $ y $ white $ white $ whe，最佳匹配的基数。我们的结果概括了Bernstein [Bernstein，2015]，该公司获得了$ 3/2 + \ Varepsilon $近似值的$ 3/2 + \ varepsilon $近似，最大的基数简单匹配。当$ w $很小时，我们的结果也会改善Gamlath等人的结果。 [Gamlath等，2019]，它获得了$2-δ$近似（对于某些小常数$δ\ sim 10^{ - 17} $），最大重量简单匹配。特别是，对于加权$ b $的问题，我们的结果是第一个超过$ 2 $的结果。我们的技术取决于最初由Bernstein和Stein [Bernstein and Stein，2015]开发的Edge-Chigre受限子图的广义加权版本。这样的子图具有有限的顶点度（因此仅使用少量边缘），并且可以轻松计算。它包含$ 2 - \ frac {1} {2W} + \ varepsilon $ the最大重量匹配的近似值，可以使用经典的kőnig -egerváry的双重定理证明。
We consider the maximum weight $b$-matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from $[1,W]$, we present a $2 - \frac{1}{2W} + \varepsilon$ approximation algorithm, using a memory of $O(\max(|M_G|, n) \cdot poly(\log(m),W,1/\varepsilon))$, where $|M_G|$ denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Bernstein, 2015], which achieves a $3/2 + \varepsilon$ approximation for the maximum cardinality simple matching. When $W$ is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a $2 - δ$ approximation (for some small constant $δ\sim 10^{-17}$) for the maximum weight simple matching. In particular, for the weighted $b$-matching problem, ours is the first result beating the approximation ratio of $2$. Our technique hinges on a generalized weighted version of edge-degree constrained subgraphs, originally developed by Bernstein and Stein [Bernstein and Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a $2 - \frac{1}{2W} + \varepsilon$ approximation of the maximum weight matching is proved using the classical Kőnig-Egerváry's duality theorem.
