## 2009 UW-PIMS Colloquium - 01

- Date: 02/20/2009

University of Washington

Recent Results on Lifted Formulations for Integer Programs

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.

Time: 14:30

Location: Mary Gates Hall 231