论文标题
超越点次突出：在线性时间内非占据自适应下调最大化
Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time
论文作者
论文摘要
在本文中，我们研究了受基数限制的非符号自适应下调最大化问题。我们首先重新访问\ citep {gotovos2015non}中提出的自适应随机贪婪算法，如果目标函数是自适应的subpodular subsodield和尖的，则他们表明该算法达到$ 1/e $的近似值。目前尚不清楚是否在自适应下调（而不诉诸于点suddodulodity）下保证。我们的第一个贡献是表明自适应的自适应随机贪婪算法在自适应supporloculation下达到了$ 1/e $的近似值。自适应随机贪婪算法的一个限制是，它需要$ o（n \ times k）$ value oracle查询，其中$ n $是地面设置的大小，$ k $是基数约束。我们的第二个贡献是开发第一个线性时间算法，用于非符号自适应的自适应下调最大化问题。我们的算法仅使用$ o（nε^{ - 2} \logε^{ - 1} { - 1}）$ yalace $ value value value value value value value value value value value value oracle询问。值得注意的是，$ o（nε^{ - 2} \logε^{ - 1}）$独立于基数约束。对于单调情况，我们提出了一种更快的算法，该算法可以通过$ O（n \ log \ frac {1}ε）$ value Oracle查询来实现预期的$ 1-1/e-ε$近似比。我们还通过考虑分区的矩阵约束来概括我们的研究，并为单调和完全自适应的下调函数开发线性时间算法。
In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint. We first revisit the adaptive random greedy algorithm proposed in \citep{gotovos2015non}, where they show that this algorithm achieves a $1/e$ approximation ratio if the objective function is adaptive submodular and pointwise submodular. It is not clear whether the same guarantee holds under adaptive submodularity (without resorting to pointwise submodularity) or not. Our first contribution is to show that the adaptive random greedy algorithm achieves a $1/e$ approximation ratio under adaptive submodularity. One limitation of the adaptive random greedy algorithm is that it requires $O(n\times k)$ value oracle queries, where $n$ is the size of the ground set and $k$ is the cardinality constraint. Our second contribution is to develop the first linear-time algorithm for the non-monotone adaptive submodular maximization problem. Our algorithm achieves a $1/e-ε$ approximation ratio (this bound is improved to $1-1/e-ε$ for monotone case), using only $O(nε^{-2}\log ε^{-1})$ value oracle queries. Notably, $O(nε^{-2}\log ε^{-1})$ is independent of the cardinality constraint. For the monotone case, we propose a faster algorithm that achieves a $1-1/e-ε$ approximation ratio in expectation with $O(n \log \frac{1}ε)$ value oracle queries. We also generalize our study by considering a partition matroid constraint, and develop a linear-time algorithm for monotone and fully adaptive submodular functions.
