Approximation Algorithms for Optimization under Uncertainty
summary
Stochastic knapsack treats item sizes (and sometimes rewards) as known distributions and compares online policies to the optimal adaptive decision tree; optimal trees can be exponentially large but have bounded adaptivity gap to simple nonadaptive lists. Key tools are LP relaxations over marginals and truncating sizes at B+ε, then rounding to a randomized policy that with 50% picks the best single item and 50% tries items in random order, giving a constant approximation. Greedy-by-value can lose a factor two in impatient-customer scheduling; greedy-by-expectation can be arbitrarily bad.
AI-written summary · about
chapters (12)
- 0:00Intro
- 1:17the premise
- 5:36what kinds of problems?
- 9:52a sketch of a history...
- 11:03example I: knapsack
- 14:29comparison to online algorithms
- 17:20solution concept: decision tree
- 19:05how do we solve stochastic knapsack?
- 23:41an LP-based algorithm
- 27:45take-aways
- 28:26an extension: stochastic orienteering
- 33:21vignettes II: impatience
related talks
33mRobust Algorithms for Secretaries and Bandits
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
43mGreedy Approximation Algorithms for Active Sequential Hypothesis Testing
44mParsimonious Learning-Augmented Algorithms
01h 01mRobustness, Stochastics, Uncertainty 2
48mA Simple Condition for Constant Regret in Online Decision-Making
43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization