%0 Report
%D 1995
%T Improved approximation guarantees for packing and covering integer programs
%A Srinivasan, Aravind
%X 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.
%B DIMACS Technical Report
%8 1995/09//
%G eng