Completed
Analysis (Monotone Functions)
Class Central Classrooms beta
YouTube playlists curated by Class Central.
Classroom Contents
Theory Seminar - Submodular Maximization
Automatically move to the next video in the Classroom when playback concludes
- 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
