Approximability of Sparse Integer Programs

Approximability of Sparse Integer Programs

0.00 Avg rating0 Votes
Article ID: iaor20116457
Volume: 61
Issue: 1
Start Page Number: 75
End Page Number: 93
Publication Date: Sep 2011
Journal: Algorithmica
Authors: ,
Keywords: programming: nonlinear
Abstract:

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Axb,0xd} 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 ϵ>0, if PNP this ratio cannot be improved to k-1-ϵ, and under the unique games conjecture this ratio cannot be improved to k-ϵ. 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:Axb,0xd} 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.

Reviews

Required fields are marked *. Your email address will not be published.