Submodular Optimization

on YouTube ↗59m

" summary

Maximizing submodular set functions under constraints uses concrete algorithms and tight ratios: greedy gives 1 - 1/e for monotone cardinality but fails for non‑monotone cuts, randomized greedy yields about 1/e in expectation, and relaxation via the multilinear extension plus continuous/measured continuous greedy on down‑closed polytopes produces provable guarantees (measured continuous greedy combined with local search reaches ~0.385). Results assume only a value oracle, rely on linear optimization over the polytope, and leave derandomization and efficiency of sampling as open problems.

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 1:02Goals of talk
3. 2:29Example 1: Adding Dessert
4. 4:24Example 2
5. 5:14Submodular Functions: More
6. 6:16Coverage functions
7. 7:08Cut (capacity) functions
8. 8:15Maximizing Submodular Functions
9. 9:52Cardinality Constraints Sk
10. 13:57Problems with Greedy Approach
11. 16:52Remedy: Random Greedy
12. 17:37Analysis (Monotone Functions)
13. 34:56Properties of the Multilinear Extension
14. 36:26Properties We Use
15. 38:05Submodular Maximization via a Relaxation
16. 39:00Approximating the Multilinear Relaxation
17. 42:44Analysis Measured Continuous Greedy
18. 45:08Analysis (cont.)
19. 46:36Improving over 1/e
20. 48:37The Combined Algorithm
21. 52:28Open Problems/Research Directions