Primal-dual RNC approximation algorithms for set cover and covering integer programs. (English) Zbl 0914.68096
Summary: 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.
MSC:
| 68W15 | Distributed algorithms |
References:
| [1] | B. Berger, J. Rompel, and P. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, in Proc. 30th IEEE Symposium on the Foundations of Computer Science, 1989, pp. 54-59. |
| [2] | Chvátal, V., A greedy heuristic for the set‐covering problem, Math. Oper. Res., 4, 233-235 (1979) · Zbl 0443.90066 |
| [3] | Dobson, Gregory, Worst‐case analysis of greedy heuristics for integer programming with nonnegative data, Math. Oper. Res., 7, 515-531 (1982) · Zbl 0498.90061 |
| [4] | U. Feige, A threshold of \(\lnn\) for approximating set cover, in Proc. 28th ACM Symposium on the Theory of Computing, 1996, pp. 312-318. · Zbl 0922.68067 |
| [5] | Johnson, DavidApproximation algorithms for combinatorial problemsJ. Comput. System Sci.91974256278Fifth Annual ACM Symposium on the Theory of Computing (Austin, Tex., 1973) |
| [6] | R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85-103. · Zbl 1467.68065 |
| [7] | M. Luby and N. Nisan, A parallel approximation algorithm for positive linear programming, in Proc. 25th ACM Symposium on Theory of Computing, 1993, pp. 448-457. · Zbl 1310.68224 |
| [8] | Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390 (1975) · Zbl 0323.05127 |
| [9] | Leighton, F.Introduction to parallel algorithms and architecturesMorgan Kaufmann1992xx+831Arrays, trees, hypercubes |
| [10] | C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, in Proc. 25th ACM Symposium on Theory of Computing, 1993, pp. 286-293. · Zbl 1310.68094 |
| [11] | Plotkin, SergeShmoys, DavidTardos, ÉvaFast approximation algorithms for fractional packing and covering problemsIEEE Comput. Soc. PressLos Alamitos, CA1991495504 |
| [12] | Raghavan, PrabhakarProbabilistic construction of deterministic algorithms: approximating packing integer programsJ. Comput. System Sci.371988130143Twenty‐Seventh Annual IEEE Symposium on the Foundations of Computer Science (Toronto, ON, 1986) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
