Submodular set function: Difference between revisions

Revision as of 06:53, 29 January 2023

Revision as of 16:10, 26 February 2023

Line 76:

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

# The unconstrained problem of minimizing a submodular function is computable in (strongly)[[polynomial time]],<ref name="IFFGLS" /><ref name="SchrijverCunningham" /> and even in [[polynomialStrongly timepolynomial|strongly-polynomial]] time.<ref name="GLSIFF" /><ref name="CunninghamSchrijver" /> Computing the [[minimum cut]] in a graph is a special case of this minimization problem.

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