Maximization of Non-Monotone Submodular Functions
Jennifer Gillenwater · 2014
A litany of questions from a wide variety of scientific disciplines can be cast as non-monotone submodular maximization problems. Since this class of problems includes max-cut, it is NP-hard. Thus, general-purpose algorithms for the class tend to be approximation algorithms. For unconstrained problem instances, one recent innovation in this vein includes an algorithm of Buchbinder et al. (2012) that guarantees a 1/2-approximation to the maximum. Building on this, for problems subject to cardinality constraints, Buch-binder et al. (2014) offer guarantees in the range [0.356, 1/2 + o(1)]. Earlier work has the best approximation factors for more complex constraints and settings. For constraints that can be characterized as a solvable polytope, Chekuri et al. (2011) provide guarantees. For the online secretary setting, Gupta et al. (2010) provide guarantees. In sum, the current body of work on non-monotone submodular maximization lays