
Discrete Mathematics and Optimization Seminar

May. 29, 2009 MC 320, 10:30
Approximability of Sparse Integer Programs
David Pritchard
University of Waterloo

We give a pair of new approximation algorithms for sparse integer
programs. First, for covering integer programs of the form min cx: Ax
= b, 0 <= x <= d, where A has at most k nonzeroes per row, we give a
kapproximation algorithm. (We assume A, b, c, d are nonnegative.) For
any k >= 2 and eps > 0, if P != NP this ratio cannot be improved to
k1eps, and under the unique games conjecture this ratio cannot be
improved to keps. A new tool used in this result is the replacement
of constraints by others that are equivalent with respect to
nonnegative integral solutions; knapsackcover inequalities are the
other important tool. Second, for packing integer programs of the form
max cx: Ax <= b, 0 <= x <= d where A has at most k nonzeroes per
aware this is the first polynomialtime approximation algorithm for
this problem with approximation ratio depending only on k, for any
k>1. Our approach starts from iterated LP relaxation, and then uses
probabilistic and greedy methods to recover a feasible solution.



