Skip to main content

In mathematics, submodular functions are set functions which usually appear in approximation algorithms, functions modeling user preferences in game theory,economics, combinatorial optimization, electrical networks and operations research.

In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the value of the function that a single element makes when added to an input set decreases as the size of the input set increases. These functions have a natural diminishing returns property which makes them suitable for many applications. The marginal gain from adding an element to a set A is at least as high as the marginal gain from adding the same element to a superset of A. Ex:V might be colors of paint in a paint manufacturer: green, red, blue, yellow, white, etc. Producing green when you are already producing yellow and blue is probably cheaper than if you were only producing some other colors.