PRIMAL-DUAL RNC APPROXIMATION ALGORITHMS FOR SET COVER AND COVERING INTEGER PROGRAMS

Authors
RAJAGOPALAN S VAZIRANI VV
Citation
S. Rajagopalan et Vv. Vazirani, PRIMAL-DUAL RNC APPROXIMATION ALGORITHMS FOR SET COVER AND COVERING INTEGER PROGRAMS, SIAM journal on computing (Print), 28(2), 1999, pp. 526-541
Citations number
12
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
2
Year of publication
1999
Pages
526 - 541
Database
ISI
SICI code
0097-5397(1999)28:2<526:PRAAFS>2.0.ZU;2-B
Abstract
We build on the classical greedy sequential set cover algorithm, in th e spirit of the primal-dual schema, to obtain simple parallel approxim ation algorithms for the set cover problem and its generalizations. Ou r algorithms use randomization, and our randomized voting lemmas may b e of independent interest. Fast parallel approximation algorithms were known before for set cover, though not for the generalizations consid ered in this paper.