Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions (Q1069444)

The problem of maximizing a pseudoboolean function (or equivalently a set function) which is supermodular, has many interesting applications e.g. in combinatorial optimization, operations research etc. Up to now, a number of special cases of pseudoboolean functions have been known, the maximization of which can be converted into the search for a maximum flow in an associated network. These were essentially the so-called negative- positive pseudoboolean functions (which, as will be noted here, turn out to be supermodular). First it is shown here how these results on negative-positive functions can be more easily derived by using the concept of conflict graph. The conflict graph approach is then generalized to extend the class of problems amenable to maximum network flow problems to the whole set of cubic supermodular pseudoboolean functions.