Maximizing Non-Monotone Submodular Functions

Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.

Authors

• Uriel Feige
• Vahab Mirrokni
• Jan Vondrák

Keywords

• Computer science
• Mathematics
• Polynomials
• Greedy algorithms
• Algorithm design and analysis
• Approximation algorithms
• Non-monotonic Function
• Submodular Function
• General Case
• Local Search
• Estimation Algorithm
• Random Set
• Nonnegative Function
• Symmetric Function
• Symmetric Case
• Hypergraph
• Constraint Satisfaction Problem
• Max-Cut
• Facility Location Problem
• Undirected
• Adaptive Algorithm
• Local Optimum
• Marginal Value
• Semidefinite Programming
• Random Solution
• Local Search Algorithm
• Hardness Results