Symmetric Submodular Function Minimization Under Hereditary Family Constraints

Details Symmetric Submodular Function Minimization Under Hereditary Family Constraints Symmetric Submodular Function Minimization Under Hereditary Family Constraints

2010-07-13

arxiv.org/abs/1007.2140v1

Computer Science

Data Structures and Algorithms

13 pages, Submitted to SODA 2011

Scientific paper

We present an efficient algorithm to find non-empty minimizers of a symmetric submodular function over any family of sets closed under inclusion. This for example includes families defined by a cardinality constraint, a knapsack constraint, a matroid independence constraint, or any combination of such constraints. Our algorithm make $O(n^3)$ oracle calls to the submodular function where $n$ is the cardinality of the ground set. In contrast, the problem of minimizing a general submodular function under a cardinality constraint is known to be inapproximable within $o(\sqrt{n/\log n})$ (Svitkina and Fleischer [2008]). The algorithm is similar to an algorithm of Nagamochi and Ibaraki [1998] to find all nontrivial inclusionwise minimal minimizers of a symmetric submodular function over a set of cardinality $n$ using $O(n^3)$ oracle calls. Their procedure in turn is based on Queyranne's algorithm [1998] to minimize a symmetric submodular

Affiliated with

Also associated with

No associations

Rating

Symmetric Submodular Function Minimization Under Hereditary Family Constraints 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 Symmetric Submodular Function Minimization Under Hereditary Family Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetric Submodular Function Minimization Under Hereditary Family Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351155