Theory and algorithms for set-function optimization

Consider maximizing a discrete function theta over the power set of a finite set V. More often than not, theta lacks any structure that can be exploited for optimization, forcing one to resort to exhaustive (and exponential) search. We propose an alternate method, based on expressing theta as the difference of two highly structured (in fact, submodular) functions, and maximizing the resultant decomposition in a branch and bound framework.;We begin by demonstrating that theta may be decomposed as f - delta, where f is submodular and delta is the cut function of a (simple, undirected) graph G = (V,E). By exploiting the graphical structure behind delta, we are able to create a sequence of submodular, increasingly tight, upper bounds fu - d&d4; which converge finitely to f - delta. Because non-negative submodular functions can be maximized to within a multiplicative factor of (⅓ -- 3n )-optimal in polynomial time (with n denoting the size of the ground set V and &egr;>0 a fixed constant), these upper bounds lead naturally to a branch and bound procedure for maximizing theta.;Next we consider problems of the form {max theta(V') | V' ∈ S}, where S is a subset system (i.e. a lower ideal). Several common combinatorial problems, such as Independent Set, fall into this category. The maximization of such functions is dealt with in two steps. First we show that if theta were submodular, then the constrained problem is equivalent to the unconstrained maximization of a certain submodular function. Second, we observe that since the upper bounds fu - d&d4; from the unconstrained case were submodular, our branch and bound algorithm can be extended to these constrained problems. An adaptation of the Local Search algorithm is introduced for the approximate solution of the ensuing relaxed problems.;We then resolve an "open question" proving that the worst case complexity bound of the (closely related) Submodular-Supermodular heuristic is exponential. Because that heuristic fails to guarantee an exact or approximately optimal solution, this implies that our algorithm matches the state of the art in complexity and easily exceeds it in solution quality.;Finally, we report some encouraging computational experience with the branch and bound procedure on two classes of "generic" problems. We conclude with a brief sketch of the frontier of this area and a proposal for future research.