Primal-dual RNC approximation algorithms for set cover and covering integer programs. (English) Zbl 0914.68096


68W15 Distributed algorithms
Full Text: DOI


[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.