95-37 Improved Approximation Guarantees for Packing and Covering Integer Programs

DIMACS TR: 95-37

Improved Approximation Guarantees for Packing and Covering Integer Programs

Author: Aravind Srinivasan

ABSTRACT
Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool to approximate them well. We present one elementary unifying property of all these integer programs, 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 algorithms for them with approximation guarantees significantly better than those known.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-37.ps.gz

DIMACS Home Page