The Benefit of Adaptivity in Stochastic Optimization

January 19, 2005
Jan Vondrak | MIT

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.

Speaker Details

I grew up and studied in Prague, Czech republic. Originally with interests mainly in theoretical physics, in 1995 I obtained a bachelor’s degree in physics at Charles University. However, gradually I became more interested in discrete mathematics and I switched to a computer science program. I worked with prof. Martin Loebl on a project bordering combinatorics and statistical physics, and I graduated with a Master’s degree in 1999. In 2000, I came to MIT. I enrolled in the PhD program in applied mathematics and started working with Michel Goemans, mainly in probabilistic combinatorics. The title of my thesis is “Probabilistic methods in combinatorial and stochastic optimization”. I defended my thesis in December 2004 and I am currently a member of the MSRI program “Probability, Algorithms and Statistical Physics” in Berkeley.