000150507 001__ 150507
000150507 005__ 20190522142433.0
000150507 022__ $$a0178-4617
000150507 0247_ $$a10.1007/s00453-010-9431-z$$2doi
000150507 02470 $$2ISI$$a000291481900005
000150507 02470 $$2ArXiv$$a0904.0859
000150507 037__ $$aARTICLE
000150507 245__ $$aApproximability of Sparse Integer Programs
000150507 269__ $$a2011
000150507 260__ $$bSpringer-Verlag$$c2010
000150507 336__ $$aJournal Articles
000150507 500__ $$aPreliminary version appeared in Proc. European Symposium on Algorithms (ESA) 2009.
000150507 500__ $$aNational Licences
000150507 520__ $$aThe 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.
000150507 6531_ $$aInteger programming
000150507 6531_ $$aApproximation algorithms
000150507 6531_ $$aLP rounding
000150507 6531_ $$aVertex Cover
000150507 6531_ $$aApproximation Algorithms
000150507 6531_ $$a2 Variables
000150507 6531_ $$aPacking
000150507 700__ $$g198587$$aPritchard, David$$0243822
000150507 700__ $$aChakrabarty, Deeparnab
000150507 773__ $$tAlgorithmica$$j61$$k1$$q75-93
000150507 8564_ $$uhttps://infoscience.epfl.ch/record/150507/files/453_2010_Article_9431.pdf$$zPUBLISHER'S VERSION$$s703545
000150507 8560_ $$falain.borel@epfl.ch
000150507 909C0 $$xU11879$$0252111$$pDISOPT
000150507 909CO $$ooai:infoscience.tind.io:150507$$qGLOBAL_SET$$pSB$$particle
000150507 917Z8 $$x198587
000150507 917Z8 $$x198587
000150507 917Z8 $$x198587
000150507 937__ $$aEPFL-ARTICLE-150507
000150507 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000150507 980__ $$aARTICLE