论文标题
同时筛子：非单调量最大化的确定性流算法
Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization
论文作者
论文摘要
在这项工作中，我们提出了一种组合性的，确定性的单通行流算法，该算法是针对基数约束（SMCC）最大化的，不一定是单调函数的问题。在这种情况下，该函数是单调的，我们的算法将减少到Badanidiyuru等人的最佳流算法。 （2014）。通常，对于任何$ \ varepsilon> 0 $，我们的算法达到$α/（1 +α） - \ varepsilon $，其中$α$是用于后处理的SMCC的离线（确定性）算法的比率。因此，如果允许指数计算时间，我们的算法确定性地达到了几乎最佳的$ 1/2 $比率。这些结果几乎与最近提出的随机流算法的结果相匹配，该算法达到了预期的相同比率。对于确定性的单通路流算法，我们的算法在多项式时间中实现了最佳近似因素，从以前的文献的$ 1/9 $提高到$ \ \ \ of $ \ of约0.2689 $。
In this work, we present a combinatorial, deterministic single-pass streaming algorithm for the problem of maximizing a submodular function, not necessarily monotone, with respect to a cardinality constraint (SMCC). In the case the function is monotone, our algorithm reduces to the optimal streaming algorithm of Badanidiyuru et al. (2014). In general, our algorithm achieves ratio $α/ (1 + α) - \varepsilon$, for any $\varepsilon > 0$, where $α$ is the ratio of an offline (deterministic) algorithm for SMCC used for post-processing. Thus, if exponential computation time is allowed, our algorithm deterministically achieves nearly the optimal $1/2$ ratio. These results nearly match those of a recently proposed, randomized streaming algorithm that achieves the same ratios in expectation. For a deterministic, single-pass streaming algorithm, our algorithm achieves in polynomial time an improvement of the best approximation factor from $1/9$ of previous literature to $\approx 0.2689$.
