|
|
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
k-approximation 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
k-1-eps, and under the unique games conjecture this ratio cannot be
improved to k-eps. A new tool used in this result is the replacement
of constraints by others that are equivalent with respect to
nonnegative integral solutions; knapsack-cover 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 polynomial-time 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.
|
|
|
|