Efficient NC algorithms for set cover with applications to learning and geometry
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
NC approximation algorithms are given for the unweighted and weighted set cover problems. The algorithms use a linear number of processors and give a cover that has at most log n times the optimal size/weight, thus matching the performance of the best sequential algorithms. The set cover algorithm is applied to learning theory, providing an NC algorithm for learning the concept class obtained by taking the closure under finite union or finite intersection of any concept class of finite VC dimension which has an NC hypothesis finder. In addition, a linear-processor NC algorithm is given for a variant of the set cover problem and used to obtain NC algorithms for several problems in computational geometry.<>Keywords
This publication has 18 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Applications of random sampling in computational geometry, IIPublished by Association for Computing Machinery (ACM) ,1988
- New applications of random sampling in computational geometryDiscrete & Computational Geometry, 1987
- ɛ-nets and simplex range queriesDiscrete & Computational Geometry, 1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 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
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975