Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations

DOI10.1137/120891502MaRDI QIDQ2848561zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans, José A. Soto

Publication date 26 September 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2140, http://hdl.handle.net/1721.1/80848

zbMATH Keywords

minimum cutsubmodular functionssymmetric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

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(sqrtn/logn)$ (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

Recommendations

• Minimizing symmetric submodular functions
• A fully combinatorial algorithm for submodular function minimization.
• scientific article; zbMATH DE number 910864
• A note on minimizing submodular functions

Cited in

(12)

• Minimizing symmetric submodular functions
• A note on the minimization of symmetric and general submodular functions
• Gomory Hu tree and pendant pairs of a symmetric submodular system
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Symmetric submodular system: contractions and Gomory-Hu tree
• Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
• A note on minimizing submodular functions
• Randomized contractions for multiobjective minimum cuts
• Some results about the contractions and the pendant pairs of a submodular system
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
• Efficient deterministic algorithms for maximizing symmetric submodular functions
• Budget and profit approximations for spanning tree interdiction

This page was built for publication: Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848561)