2009 UW-PIMS Colloquium - 01

Disjunctive programming is a classical technique for 0-1optimization in which a set of vertices of the hypercube is approximated by the convex hull of (carefully selected) polyhedra. Through the work of Lovasz, Schriver, Sherali and Adams, and others, this can be tied with the idea of 'lifting' a formulation to a higher dimensional space, again by carefully choosing additional variables.

In this talk we will first provide an overview of this subject, and then describe a new use of this idea which leads to an approximation algorithm to the "minimum" knapsack problem:

We show that for each fixed error 0 < ε < 1, there is a polynomial-time algorithm that produces a 0 - 1 vector satisfying constraint(*), whose value is at most a factor of (1 + ε) larger than the optimum. Furthermore, this approximation is obtained by rounding the solution to a linear program. This is the first such algorithm. If time permits, we will show generalizations of this result. Joint work with Ben McClosky.