Volume 8 (2012) Article 24 pp. 533-565
Solving Packing Integer Programs via Randomized Rounding with Alterations
Published: October 28, 2012
$\newcommand{\eee}{\mathrm e}$
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.