The Library
Improved approximation guarantees for packing and covering integer programs
Tools
UNSPECIFIED (1999) Improved approximation guarantees for packing and covering integer programs. SIAM JOURNAL ON COMPUTING, 29 (2). pp. 648-670. ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | SIAM JOURNAL ON COMPUTING | ||||
Publisher: | SIAM PUBLICATIONS | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 6 December 1999 | ||||
Dates: |
|
||||
Volume: | 29 | ||||
Number: | 2 | ||||
Number of Pages: | 23 | ||||
Page Range: | pp. 648-670 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |