Submodular set function: Difference between revisions

Revision as of 19:33, 21 October 2022

Revision as of 01:25, 12 November 2022

Line 74:

=== 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===

Unlike the case of minimization, maximizing a generic submodular functionsfunction is [[NP-hard]] even in the unconstrained setting. TheoryThus, and enumeration algorithms for finding local and global maxima (minima)most of submodularthe (supermodular) functions can be foundworks in B.this Goldengorin.field Europeanare Journalconcerned ofwith Operational Research 198(1):102polynomial-112, DOI: 10.1016/j.ejor.2008.08.022. 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, thetime approximation algorithms, for these problems are based on eitherincluding [[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|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 more general 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" />

Many of these algorithms can be unified within a semi-differential based framework of algorithms.<ref name="IJB" />

===Related optimization problems===