Content deleted Content added
Erel Segal (talk | contribs) |
→Submodular set function maximization: we do not need a page number within a journal article whose entire topic is this claim, and whose abstract states this claim, and our citation templates do not provide a mechanism for augmenting journal articles with page numbers that are not the whole range of page numbers for the whole article |
||
Line 86:
# The problem of maximizing a non-negative submodular function admits a 1/2 approximation algorithm.<ref name="FMV" /><ref name="BFNS" /> Computing the [[maximum cut]] of a graph is a special case of this problem.
# The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a <math>1 - 1/e</math> approximation algorithm.<ref name="NVF" />
# The problem of maximizing a monotone submodular function subject to a [[matroid]] constraint (which subsumes the case above) also admits a <math>1 - 1/e</math> approximation algorithm.<ref name="CCPV" /><ref name="FNS" /><ref name="FW" />
| |||