Theory of Computing ------------------- Title : Solving Packing Integer Programs via Randomized Rounding with Alterations Authors : Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan Volume : 8 Number : 24 Pages : 533-565 URL : https://theoryofcomputing.org/articles/v008a024 Abstract -------- 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 $(e.k+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 $(\frac{e^2 k}{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.