Monday February 14th at 4.30pm

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.