We consider approximation algorithms for packing integer programs (PIPs) of the form @math where @math , @math , and @math are nonnegative. We let @math denote the width of @math which is at least @math . Previous work by bansal-sparse obtained an @math -approximation ratio where @math is the maximum number of nonzeroes in any column of @math (in other words the @math -column sparsity of @math ). They raised the question of obtaining approximation ratios based on the @math -column sparsity of @math (denoted by @math ) which can be much smaller than @math . Motivated by recent work on covering integer programs (CIPs) cq,chs-16 we show that simple algorithms based on randomized rounding followed by alteration, similar to those of bansal-sparse (but with a twist), yield approximation ratios for PIPs based on @math . First, following an integrality gap example from bansal-sparse , we observe that the case of @math is as hard as maximum independent set even when @math . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width @math where @math , we obtain an @math -approximation. In the large width regime, when @math , we obtain an @math -approximation. We also obtain a @math -approximation when @math .
Approximation algorithms for PIPs in their general form were considered initially by Raghavan and Thompson @cite_8 and refined substantially by Srinivasan @cite_12 . Srinivasan obtained approximation ratios of the form @math when @math had entries from @math , and a ratio of the form @math when @math had entries from @math . Pritchard @cite_2 was the first to obtain a bound for PIPs based solely on the column sparsity parameter @math . He used iterated rounding and his initial bound was improved in @cite_5 to @math . The current state of the art is due to Bansal al @cite_17 . Previously we ignored constant factors when describing the ratio. In fact @cite_17 obtains a ratio of @math by strengthening the basic LP relaxation.
@cite_8 @cite_2 @cite_5 @cite_12 @cite_17
2022191808 2062075466 1993119087 782508147
We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance. 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 e>0, if P≠NP this ratio cannot be improved to k−1−e, and under the unique games conjecture this ratio cannot be improved to k−e. 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. Several important NP-hard combinatorial optimization problems can be posed as packing covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool with which to approximate them well. We present one elementary unifying property of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known. We give new approximation algorithms for packing integer programs (PIPs) by employing the method of randomized rounding combined with alterations. Our first result is a simpler approximation algorithm for general PIPs which matches the best known bounds, and which admits an efficient parallel implementation. We also extend these results to a multi-criteria version of PIPs. Our second result is for the class of packing integer programs (PIPs) that are column sparse, i. e., where there is a specified upper bound k on the number of constraints that each variable appears in. We give an (ek+ o(k))-approximation algorithm for k-column sparse PIPs, improving over previously known O(k 2 )-approximation ratios. We also generalize our result to the case of maximizing non-negative monotone submodular functions over k-column sparse packing constraints, and obtain an e 2k