Efficient NC algorithms for set cover with applications to learning and geometry

Agarwal, 1990, Partitioning arrangements of lines I: An efficient deterministic algorithm, Discrete Computat. Geom., 5, 449, 10.1007/BF02187805 Alon, 1986, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms, 7, 567, 10.1016/0196-6774(86)90019-2 Anderson, 1985 Anderson, 1990, Parallel algorithms for arrangements, 298 Awerbuch, 1989, Compact distributed data structures for adaptive routing, 479 Blumer, 1986, Learnability and the Vapnik-Chervonenkis dimension, 273 Chazelle, 1989, A deterministic view of random sampling and its use in geometry, 539 Chvatal, 1979, A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233, 10.1287/moor.4.3.233 Clarkson, 1987, New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195, 10.1007/BF02187879 Clarkson, 1988, A randomized algorithm for closest-point queries, SIAM J. Comput., 17, 830, 10.1137/0217052 Clarkson, 1989, Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 387, 10.1007/BF02187740 Edelsbrunner, 1988, The complexity of many faces in arrangements of lines and of segments, 44 Edelsbrunner, 1986, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 341, 10.1137/0215024 Haussler, 1987, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2, 127, 10.1007/BF02187876 Johnson, 1974, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 256, 10.1016/S0022-0000(74)80044-9 Karp, 1975, Reducibility among combinatorial problems Karp, 1985, A fast parallel algorithm for the maximal independent set problem, J. Assoc. Comput. Mach., 32, 762, 10.1145/4221.4226 Lovász, 1975, On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383, 10.1016/0012-365X(75)90058-8 Luby, 1986, A simple parallel algorithm for the maximal independent set problem SIAM, J. Comput., 15, 1036 Luby, 1988, Removing randomness in parallel computation without a processor penalty, 162 Matoušek, 1990, Construction on epsilon nets, Discrete Comput. Geom., 5, 427, 10.1007/BF02187804 Matoušek, 1990, Cutting hyperplane arrangements, 1 Motwani, 1989, The probabilistic method yields deterministic parallel algorithms, 8 Reif, 1987, Optimal randomized and parallel algorithms for computational geometry Reif, 1989, Polling: a new randomized sampling technique for computational geometry, 394 Sauer, 1972, On the density of families of sets, J. Combin. Theory Ser. A, 13, 145, 10.1016/0097-3165(72)90019-2 Vapnik, 1971, On uniform convergence of relative frequencies of events to their probabilities, Theory of Probab. Appl., 16, 264, 10.1137/1116025 Vitter, 1992, Learning in parallel, Inform. Comput., 96, 179, 10.1016/0890-5401(92)90047-J Goodrich, 1991, Constructing arrangements optimally in parallel, 169