Submodular Maximization with Cardinality Constraints

By Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz. 2014

341 citations recorded by the source corpus.

We consider the problem of maximizing a (non-monotone) submodular function subject to a cardinality constraint. In addition to capturing well-known combinatorial optimization problems, e.g., Max-k-Coverage and Max-Bisection, this problem has applications in other more practical settings such as natural language processing, information retrieval, and machine learning. In this work we present improved approximations for two variants of the cardinality constraint for non-monotone functions. When at most k elements can be chosen, we improve the current best 1/e -- o(1) approximation to a factor that is in the range [1/e + 0.004, 1/2], achieving a tight approximation of 1/2 -- o(1) for k = n/2 and breaking the 1/e barrier for all values of k. When exactly k elements must be chosen, our algorithms improve the current best 1/4 -- o(1) approximation to a factor that is in the range [0.356, 1/2], again achieving a tight approximation of 1/2 -- o(1) for k = n/2. Additionally, some of the algorithms we provide are very fast with time complexities of O(nk), as opposed to previous known algorithms which are continuous in nature, and thus, too slow for applications in the practical settings mentioned above. Our algorithms are based on two new techniques. First, we present a simple randomized greedy approach where in each step a random element is chosen from a set of "reasonably good" elements. This approach might be considered a natural substitute for the greedy algorithm of Nemhauser, Wolsey and Fisher [45], as it retains the same tight guarantee of 1--1/e for monotone objectives and the same time complexity of O(nk), while giving an approximation of 1/e for general non-monotone objectives (while the greedy algorithm of Nemhauser et. al. fails to provide any constant guarantee). Second, we extend the double greedy technique, which achieves a tight 1/2 approximation for unconstrained submodular maximization, to the continuous setting. This allows us to manipulate the natural rates by which elements change, thus bounding the total number of elements chosen.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias (2020, background): “For non-monotone submodular functions, there is the randomized greedy algorithm which emits a 1 /e approximation to the optimal solution (Buchbinder et al., 2014).”
Investigating Gender Bias in Language Models Using Causal Mediation Analysis (2020, background): “For non-monotone submodular functions, there is the randomized greedy algorithm which emits a 1 /e approximation to the optimal solution (Buchbinder et al., 2014).”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, methodology): “Zhou & Spanos (2016) use the submodularity index to characterize the performance of the R AN - DOM G REEDY algorithm (Buchbinder et al., 2014) for maximizing a non-monotone function.”
Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" (2017, methodology): “To compare the effect of deleting representative elements to the that of deleting random elements from the stream, we use two stochastic variants of the greedy algorithm, namely, STOCHASTIC-GREEDY (Mirzasoleiman et al., 2015) and RANDOM-GREEDY (Buchbinder et al., 2014).”
( Please , provide the manuscript number ! ) Capacity Constrained Assortment Optimization under the Markov Chain based Choice Model (2015, neutral): “We present the proof in Appendix A.”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, neutral): “[3] managed to extend the fractional version of the algorithm to handle cardinality constraints.”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, methodology): “This property has been shown to be useful for obtaining constant-factor approximations for non-monotone submodular function maximization (Buchbinder et al., 2014).”
Non-monotone Submodular Maximization in Exponentially Fewer Iterations (2018, background): “The proof generalizes an argument in [BFNS14] and is deferred to Appendix B. Lemma 2.”