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

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1989
Accession Number
ADA213975

Entities

People

  • Bonnie Berger
  • John Rompel
  • Peter W. Shor

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Science
  • Computers
  • Consistency
  • Information Processing
  • Military Research
  • Notation
  • Parallel Computing
  • Parallel Processing
  • Probability
  • Probability Distributions
  • Random Variables
  • Security
  • Standards
  • Statistical Samples
  • Symbols

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.