Published: October 28, 2012

**Keywords:**approximation algorithms, packing integer programs, submodular functions

**Categories:**algorithms, approximation algorithms, packing, integer program, submodular function, randomized rounding

**ACM Classification:**F.2.2

**AMS Classification:**68W25, 90C05, 90C10

**Abstract:**
[Plain Text Version]

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 $(\eee 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
$\smash{\left(\frac{\eee^2k}{\eee-1} + o(k) \right)}$-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.