Streaming Submodular Matching Meets the Primal-Dual Method
Streaming Submodular Matching Meets the Primal-Dual Method
复制标题
DOI：
10.1137/1.9781611976465.114
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Roie Levin;David Wajc
中科院分区：
文献类型：
--
作者：
Roie Levin;David Wajc
我们研究了流子模最大化匹配/$B$匹配约束（MSM/MSbM），并提出了改进的上限和下限为这些问题。在上界方面，我们给出了原始-对偶算法，实现了以下近似比。$\bullet $$3 +2\sqrt{2}\约为5.828$（适用于单调MSM），改善了之前7.75 $的最佳比例。$\bullet $$4 +3\sqrt{2}\对于非单调MSM，约为7.464$，提高了之前的最佳比例$9.899$。$\bullet $$3 +\n $用于最大权重b匹配，改进了之前的最佳比例$4+\n $。在下界方面，我们改进了以前的最佳下界$\frac{e}{e-1}\approximat1.582 $的MSM，并显示基于ETH的下界$\approximat1.914 $的多时间单调MSM流算法。我们最重要的贡献是算法技术。我们发现，（随机）原始-对偶方法，起源于最大权重匹配（MWM）的研究，也是有用的MSM的上下文中。据我们所知，这是第一次使用基于原始-对偶的分析进行流子模块优化。我们还展示了如何重新解释以前的算法MSM在我们的框架，因此，我们希望我们的工作是一个步骤，统一新老技术流子模块最大化，它铺平了道路，进一步的新成果。
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+\epsilon$ for maximum weight b-matching, improving the previous best ratio of $4+\epsilon$. 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.