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

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. >

Authors

• Bonnie Berger
• John Rompel
• Peter W. Shor

Keywords

• Approximation algorithms
• Greedy algorithms
• Computational geometry
• Polynomials
• Application software
• Laboratories
• Computer science
• Bridges
• Parallel algorithms
• Uninterruptible power systems
• Set Of Covariates
• Deterministic
• Lower Bound
• Total Weight
• Parallelization
• Estimation Algorithm
• Dihedral Angle
• Selection Step
• Algorithm For Problem
• Maximum Degree
• Base Classes
• Sequential Algorithm
• Polynomial-time Algorithm
• Phthalocyanine
• Vertex Degree
• Parallel Algorithm
• Convex Polygon
• Search Problem
• Hypergraph