论文标题
自适应下调最大化的线性时间算法
Linear-Time Algorithms for Adaptive Submodular Maximization
论文作者
论文摘要
在本文中，我们开发了两个随机的下管最大化问题的快速算法。我们从研究良好的自适应下调最大化问题开始，但要受到基数约束。我们开发了第一种线性时算法，该算法达到了$（1-1/e-ε）$近似比。值得注意的是，我们算法的时间复杂性为$ O（n \ log \ frac {1}ε）$（功能评估数），它独立于基数约束，其中$ n $是地面集的大小。然后，我们介绍了完全自适应的次数的概念，并开发了一种线性时间算法，以最大化完全自适应的下肠函数，但受分区的矩阵约束。我们表明，我们的算法实现了$ \ frac {1-1/e-e-ε} {4-2/e-2ε} $近似值，仅使用$ o（n \ log \ frac {1}ε）$函数评估的数量。
In this paper, we develop fast algorithms for two stochastic submodular maximization problems. We start with the well-studied adaptive submodular maximization problem subject to a cardinality constraint. We develop the first linear-time algorithm which achieves a $(1-1/e-ε)$ approximation ratio. Notably, the time complexity of our algorithm is $O(n\log\frac{1}ε)$ (number of function evaluations) which is independent of the cardinality constraint, where $n$ is the size of the ground set. Then we introduce the concept of fully adaptive submodularity, and develop a linear-time algorithm for maximizing a fully adaptive submoudular function subject to a partition matroid constraint. We show that our algorithm achieves a $\frac{1-1/e-ε}{4-2/e-2ε}$ approximation ratio using only $O(n\log\frac{1}ε)$ number of function evaluations.
