Combinatorial Optimization Reading Group - Zishen Qu

Title: Maximizing non-monotone submodular functions

Abstract:

Optimization of non-monotone submodular functions has applications in the maximum cut and maximum directed cut problems for graphs. Despite the lack of structure, we can derive rather strong results on problems of this type. We will prove that there is a deterministic algorithm producing a (1/3)-approximation for this problem. Using the value oracle model, we also have the hardness result that there can be no polynomial time (1/2+ε)-approximation. The results presented here were produced in Feige, Mirrokni, and Vondrák (2007).