Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
We present an efficient algorithm to find nonempty minimizers of a symmetric submodular function f over any family of sets I closed under inclusion. Our algorithm makes O(n[superscript 3]) oracle calls to f and I, where n is the cardinality of the ground set. In contrast, the problem of minimizing a...
Main Authors: | Goemans, Michel X., Soto, Jose A. |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Mathematics |
Format: | Article |
Language: | en_US |
Published: |
Society for Industrial and Applied Mathematics
2013
|
Online Access: | http://hdl.handle.net/1721.1/80848 https://orcid.org/0000-0002-0520-1165 |
Similar Items
-
Discrete Newton’s Algorithm for Parametric Submodular Function Minimization
by: Goemans, Michel X, et al.
Published: (2018) -
Approximating Submodular Functions Everywhere
by: Goemans, Michel X., et al.
Published: (2011) -
A simple combinatorial algorithm for submodular function minimization
by: Iwata, Satoru, et al.
Published: (2011) -
Scheduling to Minimize Power Consumption using Submodular Functions
by: Demaine, Erik D., et al.
Published: (2012) -
Scheduling to minimize power consumption using submodular functions
by: Zadimoghaddam, Morteza
Published: (2011)