Submodular set function: Difference between revisions

Revision as of 16:10, 26 February 2023

Revision as of 16:14, 26 February 2023

Line 91:

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

# TheMinimizing the difference ofbetween submodulartwo optimizationsubmodular problemfunctions<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 (see [[welfare maximization]]).<ref name="JV" />

== Applications ==