Probing to minimize

on YouTube ↗34m

" summary

Proves the first adaptive approximation for minimizing the minimum-weight element under a knapsack constraint with expected cost at most four times OPT while using budgets larger by a factor about log log M and shows adaptivity can be arbitrarily more powerful than nonadaptive. Key tools are a reduction of expectation to a sum of tail probabilities, solving threshold problems via greedy and an adaptive binary search meta-algorithm, and extensions to sum-of-smallest-K weights with a log^2 K resource augmentation.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:24What is probing?
3. 3:26Formal Model
4. 5:14What is known?
5. 6:10What is known for MinElement?
6. 7:45Max vs. Min Asymmetry
7. 9:26A Common Route
8. 10:22Hope vs. Reality
9. 11:31Our results
10. 15:06Threshold problem example
11. 17:36The Basic Idea, realized
12. 19:03Beyond the Basic Idea
13. 22:01Adaptive Binary Search
14. 27:15Mink-Knapsack: Proof Intuition
15. 30:43Conclusion