Content deleted Content added
Mathreader17 (talk | contribs) →Optimization problems: Rearrange the long paragraph into clear bullet points |
Mathreader17 (talk | contribs) →Submodular set function maximization: Adding back the citation accidentally deleted in last edit |
||
Line 79:
Unlike the case of minimization, maximizing a generic submodular function is [[NP-hard]] even in the unconstrained setting. Thus, most of the works in this field are concerned with polynomial-time approximation algorithms, including [[greedy algorithm]]s or [[local search (optimization)|local search algorithm]]s.
# The problem of maximizing a non-negative
# 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" />{{page needed|date=October 2020}}<ref>{{Cite web|last=Williamson|first=David P.|title=Bridging Continuous and Discrete Optimization: Lecture 23|url=https://people.orie.cornell.edu/dpw/orie6334/lecture23.pdf}}</ref> The [[maximum coverage problem]] is a special case of this problem.
# 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" />
| |||