%0 Conference Paper
%B Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
%D 2001
%T New approaches to covering and packing problems
%A Srinivasan, Aravind
%X Covering and packing integer programs model a large family of combinatorial optimization problems. The current-best approximation algorithms for these are an instance of the basic probabilistic method: showing that a certain randomized approach produces a good approximation with positive probability. This approach seems inherently sequential; by employing the method of alteration we present the first RNC and NC approximation algorithms that match the best sequential guarantees. Extending our approach, we get the first RNC and NC approximation algorithms for certain multi-criteria versions of these problems. We also present the first NC algorithms for two packing and covering problems that are not subsumed by the above result: finding large independent sets in graphs, and rounding fractional Group Steiner solutions on trees.
%B Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
%S SODA '01
%I Society for Industrial and Applied Mathematics
%C Philadelphia, PA, USA
%P 567 - 576
%8 2001///
%@ 0-89871-490-7
%G eng
%U http://dl.acm.org/citation.cfm?id=365411.365535