Discrete Mathematics and Optimization Seminar

Massachusetts Institute of Technology
Monday February 14th at 4.30pm
Burnside 1205

Title. The Benefit of Adaptivity in Stochastic Optimization.

Abstract. Consider the Stochastic Knapsack problem where items have deterministic values but random sizes. The motivation
for this problem is in the area of stochastic scheduling where a sequence of jobs should be scheduled on a
machine within a limited amount of time. The running times of jobs are considered random and independent. A
priori, only some information on their probability distributions is available. When a job has been scheduled and
completed, its precise running time is revealed and this information can be used in subsequent decisions. An
"adaptive policy" is a decision strategy which chooses a job to be processed based on the remaining time
available. Alternatively, we consider "non-adaptive policies" choosing a fixed ordering of jobs beforehand. A
natural question is how much advantage we can gain by being adaptive. We measure the "adaptivity gap" for a given
instance as the ratio of the expected values achieved by the optimal adaptive vs. non-adaptive policy. We are
also interested in the algorithmic questions of finding a good adaptive or non-adaptive policy efficiently.

In FOCS 2004, we showed that the adaptivity gap cannot be larger than a constant factor of 7. I will present a
recent improvement of the upper bound to 4; i.e., a non-adaptive policy which achieves at least 1/4 of the
adaptive optimum. The proof involves a new analysis of adaptive policies which leads to a polymatroid
optimization problem. Using this technique, we can also find an adaptive policy in polynomial time, which
approximates the adaptive optimum to within a factor of 3+epsilon.

Next, I will address multidimensional generalizations of the Stochastic Knapsack problem where items with random
vector sizes are to be packed in a unit hypercube ("Stochastic Packing"). I will show that for "Stochastic Set
Packing" (with random 0/1 vectors), the adaptivity gap can be as large as d^{1/2} and it is always bounded by
O(d^{1/2}). Although even deterministic Set Packing has a known inapproximability factor of d^{1/2-epsilon}, we
can approximate the adaptive optimum to within O(d^{1/2}) using a non-adaptive policy. For general Stochastic
Packing, we can only achieve an O(d)-approximation. However, we show that this is also nearly optimal, by
improving the inapproximability factor for Packing Integer Programs to d^{1-epsilon}.

This is joint work with Brian Dean and Michel Goemans.