Mathematics – Combinatorics
Scientific paper
2009-05-30
Mathematics
Combinatorics
20 pages
Scientific paper
We present a branch and bound method for maximizing an arbitrary set function h mapping 2^V to R. By decomposing h as f-g, where f is a submodular function and g is the cut function of a (simple, undirected) graph G with vertex set V, our original problem is reduced to a sequence of submodular maximization problems. We characterize a class of submodular functions, which when maximized in the subproblems, lead the algorithm to converge to a global maximizer of f-g. Two "natural" members of this class are analyzed; the first yields polynomially-solvable subproblems, the second, which requires less branching, yields NP-hard subproblems but is amenable to a polynomial-time approximation algorithm. These results are extended to problems where the solution is constrained to be a member of a subset system. Structural properties of the maximizer of f-g are also proved.
No associations
LandOfFree
Maximizing General Set Functions by Submodular Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximizing General Set Functions by Submodular Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing General Set Functions by Submodular Decomposition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-708388