On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems.

Nicole Immorlica, David R. Karger, Maria Minkoff, Vahab S. Mirrokni

Browse the full SODA paper archive.