pdf icon
Volume 8 (2012) Article 24 pp. 533-565
Solving Packing Integer Programs via Randomized Rounding with Alterations
Received: July 31, 2011
Published: October 28, 2012
Download article from ToC site:
[PDF (377K)] [PS (1626K)] [Source ZIP]
Keywords: approximation algorithms, packing integer programs, submodular functions
ACM Classification: F.2.2
AMS Classification: 68W25, 90C05, 90C10

Abstract: [Plain Text Version]

$ \newcommand{\eee}{\mathrm e} $

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.