Improved approximation guarantees for packing and covering integer programs

Improved approximation guarantees for packing and covering integer programs

0.00 Avg rating0 Votes
Article ID: iaor2001485
Country: United States
Volume: 29
Issue: 2
Start Page Number: 648
End Page Number: 670
Publication Date: Oct 1999
Journal: SIAM Journal On Computing
Authors:
Keywords: bin packing, set covering
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.

Reviews

Required fields are marked *. Your email address will not be published.