other · arXiv (Cornell University) · 2014

Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations

Soto San Martín, José

Cited by 4Open access

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

Cite this paper

APA 7

Soto San Martín, J. (2014). Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations. arXiv (Cornell University). https://doi.org/10.1137/120891502

MLA 9

Soto San Martín, José. “Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations.” arXiv (Cornell University), 2014, https://doi.org/10.1137/120891502.

Chicago

Soto San Martín, José. 2014. “Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations.” arXiv (Cornell University). https://doi.org/10.1137/120891502.

Harvard

Soto San Martín, J. (2014) ‘Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations’, arXiv (Cornell University). Available at: https://doi.org/10.1137/120891502.

BibTeX

@misc{sotosanmartin2014algorithms,
  title = {{Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations}},
  author = {Soto San Martín, José},
  journal = {arXiv (Cornell University)},
  year = {2014},
  doi = {10.1137/120891502}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.