| Speaker : | Fabien Mathieu |
| Swapcard | |
| Date: | 18/05/2022 |
| Time: | 11:00 am - 12:00 pm |
| Location: | Paris-Rennes Room (EIT Digital) |
Abstract
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.