LPs and Convex Programming Relaxations and Rounding for Stochastic Problems
summary
Projects exponential decision trees down to small LP surrogate for decision tree variables (marginals) and rounds them back into policies; assumes independent distributions and uses Markov/linearity arguments. For the best-box problem a simple randomized rounding opens each box with the LP probability and yields a 1/4 approximation (improvable to 1/2 with fancier rounding). Shows an adaptivity gap example (optimal adaptive 2.5 vs nonadaptive 2.05), discusses integrality-gap reductions to 4 and links to auction/robustness questions.
AI-written summary · about