The Power of Randomization: Efficient and Effective Algorithms for Constrained Submodular Maximization

Abstract

Submodular optimization has numerous applications such as crowdsourcing and viral marketing. In this paper, we study the fundamental problem of non-negative submodular function maximization subject to a $k$-system constraint, which generalizes many other important constraints in submodular optimization such as cardinality constraint, matroid constraint, and $k$-extendible system constraint. The existing approaches for this problem achieve the best-known approximation ratio of $k+2\sqrt{k+2}+3$ (for a general submodular function) based on deterministic algorithmic frameworks. We propose several randomized algorithms that improve upon the state-of-the-art algorithms in terms of approximation ratio and time complexity, both under the non-adaptive setting and the adaptive setting. The empirical performance of our algorithms is extensively evaluated in several applications related to data mining and social computing, and the experimental results demonstrate the superiorities of our algorithms in terms of both utility and efficiency.

arXiv commentPart of the contribution appears in ICML2021

References in corpus (6)

• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Adaptive Submodular Optimization under Matroid Constraints
• Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
• Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity
• Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time
• How Do You Want Your Greedy: Simultaneous or Repeated?