caa a22 4500 445805099 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9431-z doi (NATIONALLICENCE)springer-10.1007/s00453-010-9431-z Approximability of Sparse Integer Programs [Elektronische Daten] [David Pritchard, Deeparnab Chakrabarty] 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. Springer Science+Business Media, LLC, 2010 Integer programming nationallicence Approximation algorithms nationallicence LP rounding nationallicence Pritchard David Institute of Mathematics, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland aut Chakrabarty Deeparnab Department of Computer and Information Science, University of Pennsylvania, Philadelphia, USA aut Algorithmica Springer-Verlag 61/1(2011-09-01), 75-93 0178-4617 61:1<75 2011 61 453 https://doi.org/10.1007/s00453-010-9431-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9431-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Pritchard David Institute of Mathematics, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland aut NATIONALLICENCE 700 1- Chakrabarty Deeparnab Department of Computer and Information Science, University of Pennsylvania, Philadelphia, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 75-93 0178-4617 61:1<75 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer