Budget-Smoothed Analysis for Submodular Maximization

on YouTube ↗20m

" summary

Paper introduces budget-smoothed analysis where an adversary picks a worst-case submodular function and the budget is sampled from a fixed distribution, gives a nonconvex program to compute optimal expected approximation, and proves greedy is optimal in expectation among polynomial-time algorithms. Numerical solves show greedy often beats 1−1/e, e.g. about 67% on candidate-budget data, while a robust hardness rules out >90% for any budget distribution.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:18Motivating application: getting friends to vote
3. 0:44Monotone submodular functions
4. 1:27Monotone submodular maximization
5. 3:40What about the missing?
6. 4:19Beyond-worst-case submodular functions
7. 5:54Our approach: from an overlooked object
8. 6:27Motivation in practice: robustness
9. 7:41Motivation in theory: performance
10. 8:14Therefore, we're interested in
11. 9:19Our model: budget-smoothed analysis
12. 12:06Our results
13. 14:54In hindsight
14. 16:07Budget-smoothed analysis as beyond-worst-case performance test
15. 18:23Optimal procurement auction
16. 19:12Takeaway