Continuous Methods 3

on YouTube ↗01h 02m

" summary

Shows that a submodular set function has a convex continuous extension via the Lovász extension and a dual base polytope whose linear optimization costs O(n log n) by sorting, letting convex minimization plus threshold rounding recover exact minima. Practical methods include ellipsoid for polynomial-time solvability and subgradient descent (O(1/ε^2) iterations). For maximization the multilinear/independent extension plus a continuous greedy Frank–Wolfe style method achieves a 1-1/e approximation under matroid/budget constraints.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to optimization
2. 1:20Defining submodularity
3. 5:22Applications and examples
4. 9:48Connections to convexity
5. 13:59Continuous extensions
6. 23:18Base polytopes
7. 28:38Minimization algorithms
8. 36:13Duality and rounding
9. 44:12Submodular maximization
10. 50:07Continuous greedy algorithm
11. 55:28Generalizations and conclusion