Streaming Set Cover in Practice
Michael Barlow, Christian Konrad, Charana Nandasena · Society for Industrial and Applied Mathematics eBooks · 2021
State-of-the-art practical algorithms for solving large Set Cover instances can all be regarded as variants of the Greedy Set Cover algorithm. These algorithms maintain the input sets in memory, which yields a substantial memory footprint. In particular, in the context of massive inputs, these sets may need to be maintained on the hard disk or on external memory, and, consequently, access to these sets is slow. In this paper, we demonstrate that simple one-pass algorithms with small memory footprints are able to compete with the more involved Greedy-like algorithms for Set Cover in practice. Our experiments show that a recent Set Cover streaming algorithm by Emek and Rosén [ACM Trans. on Alg. 2016] produces covers whose sizes are on average within 8% of those produced by state-of-the-art algorithms, while using between 10 and 73 times less memory. We also provide a theoretical analysis of an extension of the Emek-Rosén algorithm to multiple passes and demonstrate that multiple passes allow us to further reduce cover sizes in practice.