Content deleted Content added
Citation bot (talk | contribs) Add: url, s2cid, author pars. 1-1. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Suggested by SemperIocundus | via #UCB_webform |
→Submodular set function maximization: {{page needed}}: couldn't identify the result in the source (or cite a more modern/legible source?) |
||
Line 64:
=== Submodular set function maximization===
Unlike the case of minimization, maximizing a submodular functions is [[NP-hard]] even in the unconstrained setting. For instance [[max cut]] is a special case even when the function is required only to be non-negative. The unconstrained problem can be shown to be inapproximable if it is allowed to be negative. There has been extensive work on constrained submodular function maximization when the functions are non-negative. Typically, the approximation algorithms for these problems are based on either [[greedy algorithm]]s or [[local search (optimization)|local search algorithm]]s. The problem of maximizing a non-negative symmetric submodular function admits a 1/2 approximation algorithm.<ref name="FMV" /> Computing the [[maximum cut]] of a graph is a special case of this problem. The more general problem of maximizing a non-negative submodular function also admits a 1/2 approximation algorithm.<ref name="BFNS" /> 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}} The [[maximum coverage problem]] is a special case of this problem. The more general problem of maximizing a monotone submodular function subject to a [[matroid]] constraint also admits a <math>1 - 1/e</math> approximation algorithm.<ref name="CCPV" /><ref name="FNS" /><ref name="FW" /> Many of these algorithms can be unified within a semi-differential based framework of algorithms.<ref name="IJB" />
===Related optimization problems===
| |||