Improved Approximation Guarantees for Packing and Covering Integer Programs

TitleImproved Approximation Guarantees for Packing and Covering Integer Programs
Publication TypeJournal Articles
Year of Publication1999
AuthorsSrinivasan A
JournalSIAM Journal on Computing
Volume29
Issue2
Pagination648 - 648
Date Published1999///
ISBN Number00975397
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 with which to approximate them well. We present one elementary unifying property of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known.

URLhttp://link.aip.org/link/SMJCAT/v29/i2/p648/s1&Agg=doi
DOI10.1137/S0097539796314240