Explore a comprehensive theory seminar on submodular maximization presented by Niv Buchbinder from Tel Aviv University. Delve into the world of combinatorial optimization problems with submodular objectives, examining their applications in economics, algorithmic game theory, and combinatorial optimization. Survey various approaches for maximizing submodular functions, discussing recent advances and open questions in the field. Learn through practical examples, including the "Adding a Dessert" scenario, and explore key concepts such as coverage functions, cut functions, and cardinality constraints. Discover algorithms like Random Greedy, Measured Continuous Greedy, and Split & Grow, along with their analyses for both monotone and non-monotone functions. Gain insights into the properties of multilinear extensions and their role in submodular maximization. Conclude with open problems and potential research directions in this fascinating area of theoretical computer science.
Overview
Syllabus
Intro
Example 1: Adding a Dessert
Example 1: Adding Dessert
Example 2
Submodular Functions: More
Coverage functions
Cut (capacity) functions
Maximizing Submodular Functions
Cardinality Constraints Sk
Problems with Greedy Approach
Interesting Questions
Remedy: Random Greedy
Analysis (Monotone Functions)
Analysis (Non-Monotone Function)
Properties of the Multilinear Extension
Properties We Use
Submodular Maximization via a Relaxation
Approximating the Multilinear Relaxation
Measured Continuous Greedy
Analysis (cont.)
Improving over 1/e
The Combined Algorithm
Deterministic Algorithms
Algorithm 1: Residual Random Greedy
Algorithm 2: Split
Final Algorithm: Split & Grow
Analysis idea
Open Problems/Research Directions
Taught by
Paul G. Allen School
