Parallel and I/O Efficient Set Covering Algorithms

This paper presents the design, analysis, and implementation of parallel and sequential I/O-efficient algorithms for set cover, tying together the line of work on parallel set cover and the line of work on efficient set cover algorithms for large, disk-resident instances. The authors' contributions are twofold: first, they design and analyze a parallel cache-oblivious set-cover algorithm that offers essentially the same approximation guarantees as the standard greedy algorithm, which has the optimal approximation. Their algorithm is the first efficient external-memory or cache-oblivious algorithm for when neither the sets nor the elements t in memory, leading to I/O cost (cache complexity) equivalent to sorting in the Cache Oblivious or Parallel Cache Oblivious models.

Provided by: Association for Computing Machinery Topic: Data Centers Date Added: Jun 2012 Format: PDF

Find By Topic