Content deleted Content added
Added free to read link in citations with OAbot #oabot |
m Grammar |
||
Line 61:
=== Submodular set function minimization===
The simplest minimization problem is to find a set <math>S\subseteq \Omega</math> which minimizes a submodular function; this is the unconstrained problem. This problem is computable in (strongly)<ref name="IFF" /><ref name="Schrijver" /> [[polynomial time]].<ref name="GLS" /><ref name="Cunningham" /> Computing the [[minimum cut]] in a graph is a special case of this general minimization problem. However, adding even a simple constraint such as a cardinality lower bound makes the minimization problem [[NP hard]], with polynomial factor lower bounds on the approximation factor.<ref name="SF" /><ref name="IJB" />
=== Submodular set function maximization===
| |||