Submodular set function: Difference between revisions

Revision as of 01:42, 12 November 2022

Revision as of 02:03, 12 November 2022

Line 96:

== Applications ==

Submodular functions naturally occur in several real world applications, in [[economics]], [[game theory]], [[machine learning]] and [[computer vision]].<ref name="KG" /><ref name="JB" /> Owing to the diminishing returns property, submodular functions naturally model costs of items, since there is often a larger discount, with an increase in the items one buys. Submodular functions model notions of complexity, similarity and cooperation when they appear in minimization problems. In maximization problems, on the other hand, they model notions of diversity, information and coverage. For more information on applications of submodularity, particularly in machine learning, see <ref name="KG" /><ref name="ST" /><ref name="JB" />

== See also ==

Line 121:

<ref name="SF">Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).</ref>

<ref name="JV">J. Vondrák, Optimal approximation for the submodular welfare problem in the value oracle model, Proc. of STOC (2008), pp. 461–471.</ref>

<ref name="ST">http://submodularity.org/.</ref>

<ref name="KG">A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008</ref>

<ref name="JB">J. Bilmes, Submodularity in Machine Learning Applications, Tutorial at AAAI-2015.</ref>

Line 144 ⟶ 143:

==External links==

* http://www.cs.berkeley.edu/~stefje/references.html has a longer bibliography

* http://submodularity.org/ includes further material on the subject

<!--- Categories --->