Towards Practical Constrained Monotone Submodular Maximization
share
We design new algorithms for maximizing a monotone non-negative submodular function under various constraints, which improve the state-of-the-art in time complexity and/or performance guarantee. We first investigate the cardinality constrained submodular maximization problem that has been widely studied for about four decades. We design an (1-1/e-ε)-approximation algorithm that makes O(n·{ε^-1, k }) queries. To the best of our knowledge, this is the fastest known algorithm. We further answer the open problem on finding a lower bound on the number of queries. We show that, no (randomized) algorithm can achieve a ratio better than (1/2+Θ(1)) with o(n/ n) queries. The acceleration above is achieved by our Adaptive Decreasing Threshold (ADT) algorithm. Based on ADT, we study the p-system and d knapsack constrained maximization problem. We show that an (1/(p+7/4d+1)-ε)-approximate solution can be computed via O(n/εn/ε{1/ε, n}) queries. Note that it improves the state of the art in both time complexity and approximation ratio. We also show how to improve the ratio for a single knapsack constraint via O(n·{ε^-1, k }) queries. For maximizing a submodular function with curvature κ under matroid constraint, we show an (1-κ/e-ε)-approximate algorithm that uses Õ(nk) value oracle queries. Our ADT could be utilized to obtain faster algorithms in other problems. To prove our results, we introduce a general characterization between randomized complexity and deterministic complexity of approximation algorithms that could be used in other problems and may be interesting in its own right.
READ FULL TEXT