Brian C. Dean Associate Professor Division of Computer Science School of Computing, Clemson University Office: McAdams Hall, Room 205 Phone: 864-656-5866 Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974 Email: bcdean@cs.clemson.edu

Adaptivity and Approximation for Stochastic Packing Problems

We study stochastic variants of Packing Integer Programs (PIP) --- the problems of finding a maximum-value 0/1 vector $x$ satisfying $Ax \leq b$, with $A$ and $b$ nonnegative. Many combinatorial problems belong to this broad class, including the knapsack problem, maximum clique, stable set, matching, hypergraph matching (a.k.a. set packing), $b$-matching, and others. PIP can also be seen as a ``multi-dimensional'' knapsack problem where we wish to pack a maximum-value collection of items with vector-valued sizes. In our stochastic setting, the vector-valued size of each item is known to us apriori only as a probability distribution, and the size of an item is instantiated once we commit to including the item in our solution.

Following the framework of [1], we consider both adaptive and non-adaptive policies for solving such problems, adaptive policies having the flexibility of being able to make decisions based on the instantiated sizes of items already included in the solution. We investigate the {\em adaptivity gap} for these problems: the maximum ratio between the expected values achieved by optimal adaptive and non-adaptive policies. We show tight bounds on the adaptivity gap for set packing and $b$-matching, and we also show how to find efficiently non-adaptive policies approximating the adaptive optimum. For instance, we can approximate the adaptive optimum for stochastic set packing to within $O(d^{1/2})$, which is not only optimal with respect to the adaptivity gap, but it is also the best known approximation factor in the deterministic case. It is known that there is no polynomial-time $d^{1/2-\epsilon}$-approximation for set packing, unless $NP = ZPP$. Similarly, for $b$-matching, we obtain algorithmically a tight bound on the adaptivity gap of $O(\lambda)$ where $\lambda$ satisfies $\sum \lambda^{b_j+1}=1$.

For general Stochastic Packing, we prove that a simple greedy algorithm provides an $O(d)$-approximation to the adaptive optimum. For $A \in [0,1]^{d \times n}$, we provide an $O(\lambda)$-approximation where $\sum 1/\lambda^{b_j} = 1$. (For $b = (B,B,\ldots,B)$, we get $\lambda = d^{1/B}$.) We also improve the hardness results for deterministic PIP: in the general case, we prove that a polynomial-time $d^{1-\epsilon}$-approximation algorithm would imply $NP=ZPP$. In the special case when $A \in [0,1]^{d \times n}$ and $b = (B,B,\ldots,B)$, we show that a $d^{1/B-\epsilon}$-approximation would imply $NP = ZPP$. Finally, we prove that it is PSPACE-hard to find the optimal adaptive policy for Stochastic Packing in any fixed dimension $d \geq 2$.

[1] Brian C. Dean, Michel X.Goemans, and Jan Vondrak. The Benefit of Adaptivity: Approximating the Stochastic Knapsack Problem. Proceedings of the 45th annual IEEE Symposium on the Foundations of Computer Science (FOCS), pages 208-217, 2004.

Available in pdf and postscript.