Abstract: Scheduling problems involve the assignment of a set of jobs to a set of machines over time. In a stochastic setting, where the processing times are known only with some uncertainty, the goal is to compute a scheduling policy that maximizes the expected value (or minimizes the expected cost) according to some objective function. As jobs are scheduled and processing times become known, the scheduler may do well to adapt the policy accordingly. Ignoring the difficulty of actually computing an adaptive policy, we might ask, "What is the largest possible ratio of expected values achieved by optimal adaptive / non-adaptive policies?"

In this talk, I'll present work by Dean, Vondrak, and Goemans that introduces this "adaptivity gap" and bounds it for a stochastic variant of the 0/1 knapsack problem where item values are deterministic and item sizes are independently drawn from known arbitrary distributions.