Linear-Time Algorithms for Adaptive Submodular Maximization
This work provides efficient algorithms for stochastic optimization problems, which is incremental but improves computational speed in machine learning and operations research.
The paper tackles the problem of adaptive submodular maximization by developing linear-time algorithms that achieve approximation ratios of (1-1/e-ε) for cardinality constraints and (1-1/e-ε)/(4-2/e-2ε) for partition matroid constraints, using O(n log(1/ε)) function evaluations.
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.