Servers

Parallel and I/O Efficient Set Covering Algorithms

Download Now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 468.39 KB