From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Fri Jul 02 2004 - 14:57:34 PDT
You are invited to attend...
************************************************************************
*****************************
WHO: Michel Goemans
AFFILIATION: M.I.T
TITLE: Adaptivity and Approximation for Packing Problems
WHEN: Wed 7/07/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 3:30PM-5:00PM
HOST: Jennifer Chayes and Kamal Jain
************************************************************************
******************************
ABSTRACT:
We consider a stochastic multi-stage variant of the NP-hard 0/1 knapsack
problem in which item values are deterministic and item sizes are
independent random variables with known, arbitrary distributions. Items
are placed in the knapsack sequentially, and the act of placing an item
in the knapsack instantiates its size. Our goal is to compute a policy
that maximizes the expected value of items placed in the knapsack, and
we consider both non-adaptive policies (that designate a priori a fixed
sequence of items to insert) and adaptive policies (whose decision of
which item to place in the knapsack depends on the sizes of items placed
in it thus far). We prove that finding an optimal adaptive policy is
PSPACE-hard. We show that adaptivity provides only a constant-factor
improvement by demonstrating a greedy non-adaptive algorithm that
approximates the optimal adaptive policy within a factor of $8.5$. We
also design an adaptive polynomial-time algorithm which approximates the
optimal adaptive policy within a factor of $5+\epsilon$, for any
constant $\epsilon > 0$.
We will also discuss extensions to other models, including set packing
and vector packing. Our results there indicate that the adaptivity gap
closely matches the deterministic approximability gap. For example, for
stochastic vector packing, we show algorithmically that the adaptivity
gap is $\Theta(\sqrt{d})$ while, in the deterministic setting, it is
known that approximating set packing within $O(d^{1/2-\epsilon})$ in
polytime would imply $NP=ZPP$.
This is joint work with Brian Dean and Jan Vondrak.
BIO:
Michel Goemans is visiting the theory group from M.I.T. where he is a
Professor of Applied Mathematics. His research interests gravitate
around combinatorial optimization. He was awarded the Fulkerson prize
for his work on the use of semidefinite programming for approximation
algorithms.
This archive was generated by hypermail 2.1.6 : Fri Jul 02 2004 - 14:58:07 PDT