Solving packing integer programs via randomized rounding with alterations

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^2/(e-1) +o(k))-approximation algorithm. In obtaining this result, we prove a new property of submodular functions that generalizes the fractional subadditivity property, which might be of independent interest.