Maximizing Non-Monotone Submodular Functions

Uriel Feige, Vahab Mirrokni, J. Vondrák

Annual Symposium on Foundations of Computer Science · 2007 · 28 citations · 0 references

Concepts

Abstract

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.