Primal-dual RNC approximation algorithms for set cover and covering integer programs

被引：0

作者：

Rajagopalan, S

Vazirani, VV

机构：

[1] Princeton Univ, DIMACS, Princeton, NJ 08544 USA

[2] Univ Calif Berkeley, Berkeley, CA 94720 USA

[3] Indian Inst Technol, Delhi, India

[4] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 28卷 / 02期

关键词：

algorithms; set cover; primal-dual; parallel; approximation; voting lemmas;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 the generalizations considered in this paper.

引用

页码：526 / 541

页数：16

共 12 条

[1]

[Anonymous], 1996, P 28 ACM S THEOR COM

[2]

BERGER B, 1989, P 30 IEEE S FDN COMP, P54

[3]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[4] WORST-CASE ANALYSIS OF GREEDY HEURISTICS FOR INTEGER PROGRAMMING WITH NONNEGATIVE DATA [J].

DOBSON, G .

MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (04) :515-531

[5] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].

JOHNSON, DS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) :256-278

[6]

Karp R. M., 1972, PROC IEEE 50 ANN S F, P85, DOI DOI 10.1007/978-1-4684-2001-2_9

[7]

Leighton F.T., 1992, Introduction to Parallel Algorithms and Architecture: Arrays. Trees. Hypercubes

[8]

LOVASZ L, DISCRETE MATH, V13, P383

[9]

Luby M., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P448, DOI 10.1145/167088.167211

[10]

Lund C., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P286, DOI 10.1145/167088.167172

← 1 2 →