Introduction to submodular functions

Speaker : Fabien Mathieu
Date: 18/05/2022
Time: 11:00 am - 12:00 pm
Location: Paris-Rennes Room (EIT Digital)


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.