论文标题
流式下匹配符合原始偶的方法
Streaming Submodular Matching Meets the Primal-Dual Method
论文作者
论文摘要
我们研究流媒体的最大化，但要受匹配/$ b $匹配的约束（MSM/MSBM），并针对这些问题进行了改进的上限和下限。在上边界，我们给出了原始的二次算法，以达到以下近似比。 $ \ bullet $ 3+2 \ sqrt {2} \ monotone MSM约5.828 $，提高了以前的最佳比率$ 7.75 $。 $ \ bullet $ 4+3 \ sqrt {2} \大约7.464 $，对于非主持酮MSM，提高了先前的最佳比率$ 9.899 $。 $ \ bullet $ 3+ε$用于最大重量B匹配，提高了以前的最佳比率$ 4+ε$。 在较低的方面，我们改进了MSM的$ \ frac {e} {E} {e-1} \大约1.582 $的最佳下限，并显示poly Time Monotone MSM流媒体流算法的基于ETH的下限$ \约1.914 $。 我们最重要的贡献是我们的算法技术。我们表明，起源于最大重量匹配（MWM）的（随机）原始偶对偶的方法在MSM的背景下也很有用。据我们所知，这是基于原始偶的分析用于流次传输优化的首次使用。我们还展示了如何在我们的框架中重新解释MSM的先前算法；因此，我们希望我们的工作是统治流式传输suplodular最大化的新技术迈出的一步，并为进一步的新结果铺平了道路。
We study streaming submodular maximization subject to matching/$b$-matching constraints (MSM/MSbM), and present improved upper and lower bounds for these problems. On the upper bounds front, we give primal-dual algorithms achieving the following approximation ratios. $\bullet$ $3+2\sqrt{2}\approx 5.828$ for monotone MSM, improving the previous best ratio of $7.75$. $\bullet$ $4+3\sqrt{2}\approx 7.464$ for non-monotone MSM, improving the previous best ratio of $9.899$. $\bullet$ $3+ε$ for maximum weight b-matching, improving the previous best ratio of $4+ε$. On the lower bounds front, we improve on the previous best lower bound of $\frac{e}{e-1}\approx 1.582$ for MSM, and show ETH-based lower bounds of $\approx 1.914$ for polytime monotone MSM streaming algorithms. Our most substantial contributions are our algorithmic techniques. We show that the (randomized) primal-dual method, which originated in the study of maximum weight matching (MWM), is also useful in the context of MSM. To our knowledge, this is the first use of primal-dual based analysis for streaming submodular optimization. We also show how to reinterpret previous algorithms for MSM in our framework; hence, we hope our work is a step towards unifying old and new techniques for streaming submodular maximization, and that it paves the way for further new results.
