Name
Abstract | ||
|---|---|---|
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. Our contributions are twofold: First, we 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. Our algorithm is the first efficient external-memory or cache-oblivious algorithm for when neither the sets nor the elements fit in memory, leading to I/O cost (cache complexity) equivalent to sorting in the Cache Oblivious or Parallel Cache Oblivious models. The algorithm also implies elow cache misses on parallel hierarchical memories (again, equivalent to sorting). Second, building on this theory, we engineer variants of the theoretical algorithm optimized for different hardware setups. We provide experimental evaluation showing substantial speedups over existing algorithms without compromising the solution's quality. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2312005.2312024 | SPAA |
Keywords | Field | DocType |
theoretical algorithm,o-efficient algorithm,parallel set cover,cache oblivious,parallel cache-oblivious,parallel hierarchical memory,set-cover algorithm,standard greedy algorithm,efficient set cover algorithm,o efficient set,cache-oblivious algorithm,approximation algorithms,external memory,parallel algorithms,greedy algorithm,external memory algorithms,set cover,parallel algorithm | Analysis of parallel algorithms,Approximation algorithm,Cache-oblivious algorithm,Cache,Computer science,Parallel algorithm,Parallel computing,Algorithm,Cache algorithms,Probabilistic analysis of algorithms,Out-of-core algorithm,Distributed computing | Conference |
Citations | PageRank | References |
14 | 0.88 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guy E. Blelloch | 1 | 2927 | 207.30 |
| Harsha Vardhan Simhadri | 2 | 226 | 13.35 |
| Kanat Tangwongsan | 3 | 357 | 20.05 |