Maximizing Non-Monotone Submodular Functions IV: Smooth Local Search Achieves 2/5 of the OptimumResearch Paper
Many optimization problems ask for a subset of a finite ground set that maximizes a submodular function, a set function with diminishing marginal returns. Max Cut and Max Directed Cut in graphs, facility location with fixed costs, and the maximization of mutual information or entropy of a subset of random variables are all of this form. Unlike the monotone…