150507
20190522142433.0
0178-4617
doi
10.1007/s00453-010-9431-z
ISI
000291481900005
ArXiv
0904.0859
ARTICLE
Approximability of Sparse Integer Programs
Springer-Verlag
2010
2011
Journal Articles
Preliminary version appeared in Proc. European Symposium on Algorithms (ESA) 2009.
National Licences
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 (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
Vertex Cover
Approximation Algorithms
2 Variables
Packing
243822
Pritchard, David
198587
Chakrabarty, Deeparnab
61
1
75-93
Algorithmica
703545
http://infoscience.epfl.ch/record/150507/files/453_2010_Article_9431.pdf
PUBLISHER'S VERSION
alain.borel@epfl.ch
252111
DISOPT
U11879
oai:infoscience.tind.io:150507
SB
article
GLOBAL_SET
198587
198587
198587
EPFL-ARTICLE-150507
EPFL
REVIEWED
PUBLISHED
ARTICLE