TY - RPRT
T1 - Improved approximation guarantees for packing and covering integer programs
Y1 - 1995
A1 - Srinivasan, Aravind
AB - 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.
JA - DIMACS Technical Report
ER -