论文标题
快速流算法在线性时间内最大化单调下函数
Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time
论文作者
论文摘要
我们考虑了单调的问题，在尺寸$ n $的地面套件的地面上最大化，但受到基数约束$ k $。对于这个问题，我们介绍了第一个具有线性时间复杂性的确定性算法。这些算法是流算法。对于任何$ c \ ge 1 $，我们的单通算法以$ \ lceil n / c \ rceil + c $ oracle查询获得恒定比率。此外，我们提出了一种确定性的多通流媒体算法，并具有恒定数量的通过数，几乎可以通过线性查询和时间复杂性达到最佳比例。我们证明了一个下限，即使允许对不可行的集合进行查询，也意味着不存在$ o（n）$ Queries的恒定因子近似。经验分析表明，我们的算法需要更少的查询（通常小于$ n $），但仍比当前最新算法（包括单通道，多通和非流程算法）获得更好的客观价值。
We consider the problem of monotone, submodular maximization over a ground set of size $n$ subject to cardinality constraint $k$. For this problem, we introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in $\lceil n / c \rceil + c$ oracle queries, for any $c \ge 1$. In addition, we propose a deterministic, multi-pass streaming algorithm with a constant number of passes that achieves nearly the optimal ratio with linear query and time complexities. We prove a lower bound that implies no constant-factor approximation exists using $o(n)$ queries, even if queries to infeasible sets are allowed. An empirical analysis demonstrates that our algorithms require fewer queries (often substantially less than $n$) yet still achieve better objective value than the current state-of-the-art algorithms, including single-pass, multi-pass, and non-streaming algorithms.
