Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39172
Title: Improved approximation guarantees for packing and covering integer programs
Authors: Srinivasan, A. 
Issue Date: 1999
Source: Srinivasan, A. (1999). Improved approximation guarantees for packing and covering integer programs. SIAM Journal on Computing 29 (2) : 648-670. ScholarBank@NUS Repository.
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 properly 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.
Source Title: SIAM Journal on Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/39172
ISSN: 00975397
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

53
checked on Jan 20, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.