Efficient NC Algorithms for Set Cover Applications to Learning and Geometry.

摘要

In this paper we give NC approximation algorithms for the unweighted and weighted set cover problems. Our 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 (H, Lo, C). We apply our set cover algorithm to learning theory, giving an NC algorithm to learn 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, we give a linear-processor NC algorithm for a variant of the set cover problem first proposed by (cf), and use it to obtain NC algorithms for several problems in computational geometry. (KR)