Maximizing General Set Functions by Submodular Decomposition Export

@article{citeulike:5038026, abstract = {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.}, archivePrefix = {arXiv}, author = {Byrnes, Kevin}, citeulike-article-id = {5038026}, citeulike-linkout-0 = {http://arxiv.org/abs/0906.0120}, citeulike-linkout-1 = {http://arxiv.org/pdf/0906.0120}, comment = {Optimize any set function (though some allow only approximations) by decomposing it into a submodular function and the cut function of a graph.}, eprint = {0906.0120}, keywords = {graph\_theory, optimization, submodularity}, month = {May}, posted-at = {2009-07-02 01:19:25}, priority = {2}, title = {Maximizing General Set Functions by Submodular Decomposition}, url = {http://arxiv.org/abs/0906.0120}, year = {2009} }

TY - JOUR ID - citeulike:5038026 L3 - citeulike-article-id:5038026 N2 - 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. TI - Maximizing General Set Functions by Submodular Decomposition KW - graph_theory KW - optimization KW - submodularity N1 - Optimize any set function (though some allow only approximations) by decomposing it into a submodular function and the cut function of a graph. AU - Byrnes, Kevin PY - 2009/May/30/ UR - http://arxiv.org/abs/0906.0120 ER -