Primal-dual RNC approximation algorithms for set cover and covering integer programs
S Rajagopalan, VV Vazirani - SIAM Journal on Computing, 1998 - SIAM
S Rajagopalan, VV Vazirani
SIAM Journal on Computing, 1998•SIAMWe build on the classical greedy sequential set cover algorithm, in the spirit of the primal-
dual schema, to obtain simple parallel approximation algorithms for the set cover problem
and its generalizations. Our algorithms use randomization, and our randomized voting
lemmas may be of independent interest. Fast parallel approximation algorithms were known
before for set cover, thoughnot for the generalizations considered in this paper.
dual schema, to obtain simple parallel approximation algorithms for the set cover problem
and its generalizations. Our algorithms use randomization, and our randomized voting
lemmas may be of independent interest. Fast parallel approximation algorithms were known
before for set cover, thoughnot for the generalizations considered in this paper.
We build on the classical greedy sequential set cover algorithm, in the spirit of the primal-dual schema, to obtain simple parallel approximation algorithms for the set cover problem and its generalizations. Our algorithms use randomization, and our randomized voting lemmas may be of independent interest. Fast parallel approximation algorithms were known before for set cover, thoughnot for the generalizations considered in this paper.
Society for Industrial and Applied Mathematics