Submodular set function: Difference between revisions

Revision as of 01:30, 12 November 2022

Revision as of 01:42, 12 November 2022

Line 74:

=== Submodular set function minimization===

The hardness of minimizing a submodular set function depends on constraints imposed on the problem.

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" />

# The simplest minimizationunconstrained problem is to find a set <math>S\subseteq \Omega</math> whichof minimizesminimizing 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" />

# The problem of minimizing a submodular function with a cardinality lower bound is [[NP-hard]], with polynomial factor lower bounds on the approximation factor.<ref name="SF" /><ref name="IJB" />

=== Submodular set function maximization===

Line 86 ⟶ 89:

===Related optimization problems===

Apart from submodular minimization and maximization, there are several other natural optimization problems related to submodular functions.

Apart from submodular minimization and maximization, another natural problem is Difference of Submodular Optimization.<ref name="NB" /><ref name="IBUAI" /> Unfortunately, this problem is not only NP hard, but also inapproximable.<ref name="IBUAI" /> A related optimization problem is minimize or maximize a submodular function, subject to a submodular level set constraint (also called submodular optimization subject to submodular cover or submodular knapsack constraint). This problem admits bounded approximation guarantees.<ref name="IB" /> Another optimization problem involves partitioning data based on a submodular function, so as to maximize the average welfare. This problem is called the submodular welfare problem.<ref name="JV" />

# The difference of submodular optimization problem<ref name="NB" /> is not only NP hard, but also inapproximable.<ref name="IBUAI" />

# Minimization/maximization of a submodular function subject to a submodular level set constraint (also known as submodular optimization subject to submodular cover or submodular knapsack constraint) admits bounded approximation guarantees.<ref name="IB" />

# Partitioning data based on a submodular function to maximize the average welfare is known as the submodular welfare problem, which also admits bounded approximation guarantees.<ref name="JV" />

== Applications ==