Logo image
Back
Faster Set Cover in the MPC Model
Journal article   Open access   Peer reviewed

Faster Set Cover in the MPC Model

Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju and Joshua Sobel
Theoretical computer science, Vol.1086(21 October 2026), 116238
09/12/2026
DOI: 10.1016/j.tcs.2026.116238
url
https://doi.org/10.1016/j.tcs.2026.116238View
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 O˜(logN)-rounds in the linear-memory MPC model and in O˜(log1.5N) 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(log2N) 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).
 Parallel set cover Massively parallel computing model Approximation algorithms

Details

Metrics

2 Record Views
Logo image