Maximizing Non-Monotone Submodular Functions II: A Nonadaptive Algorithm Achieves 1/3 of the OptimumResearch Paper
Maximizing a submodular set function without constraints contains Max Cut, Max Directed Cut, maximum facility location and several graph and hypergraph cut problems as special cases, and it appears in operations research wherever a value exhibits diminishing returns but is not monotone (profit that combines coverage with a cost, for example). These problems…