|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Symmetric Submodular Function Minimization Under Hereditary Family Constraints | | Michel X. Goemans
; José A. Soto
; | | Date: |
13 Jul 2010 | | Abstract: | 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 | | Source: | arXiv, 1007.2140 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER