Back to Search
Start Over
Approximability of Sparse Integer Programs.
- Source :
-
Algorithmica . Sep2011, Vol. 61 Issue 1, p75-93. 19p. - Publication Year :
- 2011
-
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: 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 ε>0, if P≠ NP 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: Ax≤ b, 0≤ x≤ d} where A has at most k nonzeroes per column, we give a (2 k+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 is small compared to b. Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 61
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 61190694
- Full Text :
- https://doi.org/10.1007/s00453-010-9431-z