Submodular set function: Difference between revisions

Revision as of 10:39, 26 September 2023

Revision as of 20:30, 13 October 2023

Line 1:

{{Short description|Set-to-real map with diminishing returns}}

{{Cleanup bare URLs|date=September 2022}}

{{Use American English|date = January 2019}}

In mathematics, a '''submodular set function''' (also known as a '''submodular function''') is a [[set function]] that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit ([[diminishing returns]]). The natural [[diminishing returns]] property which makes them suitable for many applications, including [[approximation algorithms]], [[game theory]] (as functions modeling user preferences) and [[electrical network]]s. Recently, submodular functions have also found immense utility in several real world problems in [[machine learning]] and [[artificial intelligence]], including [[automatic summarization]], [[multi-document summarization]], [[feature selection]], [[Active learning (machine learning)|active learning]], sensor placement, image collection summarization and many other domains.<ref name="LB" /><ref name="TIWB" /><ref name="KG1" /><ref name="KG" />