Approximability of Sparse Integer Programs
The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Axa parts per thousand yenb,0a parts per thousand currency signxa parts per thousand currency signd} 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 ka parts per thousand yen2 and epsilon > 0, if P not equal NP this ratio cannot be improved to k-1-epsilon, and under the unique games conjecture this ratio cannot be improved to k-epsilon. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx:Axa parts per thousand currency signb,0a parts per thousand currency signxa parts per thousand currency signd} where A has at most k nonzeroes per column, we give a (2k (2)+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A (ij) is small compared to b (i) . Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.
integer programming approximation algorithms lp rounding