Submodularity is a property that models “diminishing return”, when the benefits of adding a new element to a set decreases with the size of the set. One of its main advantages is a guarantee on the performance of greedy algorithms for problems where the optimal solution is NP-hard.
This session aims at presenting submodular functions at a beginners’ level:
- Equivalent definitions;
- A few practical examples of submodular functions;
- (1-1/e) approximation under cardinality constraints.