Improved Approximation Guarantees for Packing and Covering Integer Programs

Simple item page
dc.contributor.authorAravind Srinivasanen_US
dc.date.accessioned2004-10-21T14:28:52Zen_US
dc.date.accessioned2017-01-23T06:59:52Z
dc.date.available2004-10-21T14:28:52Zen_US
dc.date.available2017-01-23T06:59:52Z
dc.date.issued1995-10-01T00:00:00Zen_US
dc.description.abstractSeveral 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. Part of this work was done while at the School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA, supported by grant 93-6-6 of the Alfred P. Sloan Foundation to the Institute for Advanced Study. Part of this work was done while at DIMACS, supported by NSF grant NSF-STC91-19999 to DIMACS and by support to DIMACS from the New Jersey Commission on Science and Technology. Part was done while visiting the Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK, supported in part by the ESPRIT Basic Research Action Programme of the EC under contract No. 7141 (project ALCOM II).en_US
dc.format.extent272869 bytesen_US
dc.format.extent285695 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/postscripten_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1395en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTR10/95en_US
dc.titleImproved Approximation Guarantees for Packing and Covering Integer Programsen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
report.ps
Size:
279 KB
Format:
Postscript Files
Description:
Download
Thumbnail Image
Name:
report.pdf
Size:
266.47 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.52 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports