Improved approximation guarantees for packing and covering integer programs

TitleImproved approximation guarantees for packing and covering integer programs
Publication TypeReports
Year of Publication1995
AuthorsSrinivasan A
Series TitleDIMACS Technical Report
Date Published1995/09//
Abstract

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.