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.