DocumentCode
2366495
Title
Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs
Author
Rajagopalan, Sridhar ; Vazirani, V.V.
Author_Institution
California Univ., Berkeley, CA, USA
fYear
1993
fDate
3-5 Nov 1993
Firstpage
322
Lastpage
331
Abstract
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, though not for any of its generalizations
Keywords
computational geometry; parallel algorithms; classical greedy sequential set cover algorithm; covering integer programs; parallel approximation algorithms; primal-dual RNC approximation algorithms; randomization; randomized voting; set cover problem; Algorithm design and analysis; Approximation algorithms; Cost function; Greedy algorithms; Linear programming; Parallel algorithms; Voting;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location
Palo Alto, CA
Print_ISBN
0-8186-4370-6
Type
conf
DOI
10.1109/SFCS.1993.366855
Filename
366855
Link To Document