Title: Maximizing non-monotone submodular functions
|Affiliation:||University of Waterloo|
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).
200 University Avenue West
Waterloo, ON N2L 3G1