Logo image
Back
Faster Set Cover in the MPC Model
Conference proceeding   Open access

Faster Set Cover in the MPC Model

Hongyan Ji, Shreyas Pai, Sriram Pemmaraju and Joshua Sobel
Proceedings of the 26th International Conference on Distributed Computing and Networking, pp.144-151
ACM Other Conferences
ICDCN 2025: 26th International Conference on Distributed Computing and Networking
01/04/2025
DOI: 10.1145/3700838.3700861
Appears in  UI Libraries Support Open Access
url
https://doi.org/10.1145/3700838.3700861View
Published (Version of record) Open Access

Abstract

The Massively Parallel Computation (MPC) model is a popular abstraction for large-scale distributed computing. The Set Cover problem is a classical combinatorial optimization problem that has a wide variety of applications and generalizes many well-studied problems such as vertex cover, edge cover, and minimum dominating set. For a Set Cover instance with a ground set of n elements and a collection of m sets, we present two O(log n)-approximation algorithms in the MPC model. Our algorithms run in \(\tilde{O}(\log N) \)-rounds in the linear-memory MPC model and in \(\tilde{O}(\log ^{1.5} N) \) rounds in the sublinear-memory MPC model, where N = n + m. These are the first O(log n)-approximation algorithms for Set Cover in this setting that run in o(log 2N) rounds. Our results are obtained by repurposing the sparsified graph exponentiation technique that has been successful for the maximal independent set problem in the MPC model and applying it to a simple, distributed Set Cover algorithm by Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020).
 Theory of computation -- Distributed algorithms Theory of computation -- Massively parallel algorithms Theory of computation -- Models of computation UIOWA OA Agreement

Details

Metrics

9 Record Views
Logo image