Efficient NC algorithms for set cover with applications to learning and geometry
Authors:
- Bonnie BergerBBBonnie Berger
- John RompelJRJohn Rompel
- Peter W. ShorPSPeter W. Shor
- 1 December 1994
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 49 (3) , 454-477
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Learning in parallelInformation and Computation, 1992
- A Randomized Algorithm for Closest-Point QueriesSIAM Journal on Computing, 1988
- ɛ-nets and simplex range queriesDiscrete & Computational Geometry, 1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Constructing Arrangements of Lines and Hyperplanes with ApplicationsSIAM Journal on Computing, 1986
- A fast parallel algorithm for the maximal independent set problemJournal of the ACM, 1985
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975
- Approximation algorithms for combinatorial problemsJournal of Computer and System Sciences, 1974
- On the density of families of setsJournal of Combinatorial Theory, Series A, 1972
- On the Uniform Convergence of Relative Frequencies of Events to Their ProbabilitiesTheory of Probability & Its Applications, 1971