Recent Results on Maximizing Submodular Functions

Explore recent advancements in submodular maximization through this comprehensive lecture, covering both constrained and unconstrained scenarios, as well as monotone and non-monotone submodular functions. Delve into key concepts such as decreasing marginals, modular functions, and the value oracle model. Examine the differences between unconstrained and constrained optimization, and learn about the directed case and its historical context. Gain insights into greedy algorithms, randomization techniques, and relaxations, including the multilinear extension. Investigate constraints and their impact on optimization, and understand the continuous greedy algorithm and its application to the modular welfare problem. This in-depth presentation, part of the Hausdorff Trimester Program on Combinatorial Optimization, offers a thorough exploration of cutting-edge research in submodular function maximization.

Introduction
Definition
Decreasing Marginals
Modular Functions
Optimization
Value Oracle Model
Unconstrained vs Unconstrained
Submodular functions
Directed case
History
Greedy
Algorithm
Main Observation
Analysis
Randomization
Relaxations
MultiLinear Extension
Constraints
Continuous Greedy
Modular Welfare Problem
Continuous Greedy Algorithm