Improved approximation guarantees for packing and covering integer programs

Several important NP-hard combinatorial optimization problems canbe posed as packing/covering integer programs; the randomized rounding
technique of Raghavan & Thompson is a powerful tool to approximate
them well. We present one elementary unifying property of all these in-
teger programs (IPs), and use the FKG correlation inequality to derive
an improved analysis of randomized rounding on them. This also yields a
pessimistic estimator, thus presenting deterministic polynomial-time algo-
rithms for them with approximation guarantees signi cantly better than
those known.