Computer Science – Data Structures and Algorithms
Scientific paper
2009-04-06
Computer Science
Data Structures and Algorithms
Version submitted to Algorithmica special issue on ESA 2009. Previous conference version: http://dx.doi.org/10.1007/978-3-642-
Scientific paper
The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {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. 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: Ax <= b, 0 <= x <= d} 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.
Chakrabarty Deeparnab
Pritchard David
No associations
LandOfFree
Approximability of Sparse Integer Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximability of Sparse Integer Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximability of Sparse Integer Programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-132941