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.