Theory Seminar - Submodular Maximization

Theory Seminar - Submodular Maximization

Paul G. Allen School via YouTube Direct link

Properties of the Multilinear Extension

15 of 28

15 of 28

Properties of the Multilinear Extension

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Theory Seminar - Submodular Maximization

Automatically move to the next video in the Classroom when playback concludes

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.