Posimodular Function Optimization

A function Open image in new window on a finite set V is posimodular if \(f(X)+f(Y) \ge f(X\setminus Y)+f(Y\setminus X)\), for all \(X,Y\subseteq V\). Posimodular functions often arise in combinatorial optimization such as undirected cut functions. We consider the problem of finding a nonempty subset X minimizing f(X), when the posimodular function f is given by oracle access.