Главная
Study mode:
on
1
Intro
2
Example 1: Adding a Dessert
3
Example 1: Adding Dessert
4
Example 2
5
Submodular Functions: More
6
Coverage functions
7
Cut (capacity) functions
8
Maximizing Submodular Functions
9
Cardinality Constraints Sk
10
Problems with Greedy Approach
11
Interesting Questions
12
Remedy: Random Greedy
13
Analysis (Monotone Functions)
14
Analysis (Non-Monotone Function)
15
Properties of the Multilinear Extension
16
Properties We Use
17
Submodular Maximization via a Relaxation
18
Approximating the Multilinear Relaxation
19
Measured Continuous Greedy
20
Analysis (cont.)
21
Improving over 1/e
22
The Combined Algorithm
23
Deterministic Algorithms
24
Algorithm 1: Residual Random Greedy
25
Algorithm 2: Split
26
Final Algorithm: Split & Grow
27
Analysis idea
28
Open Problems/Research Directions
Description:
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.

Theory Seminar - Submodular Maximization

Paul G. Allen School
Add to list