2026-07-24T08:23:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21245 2024-10-24T07:40:08Z ddc:004 open_access

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling Dhulipala, Laxman Dinitz, Michael Łącki, Jakub Mitrović, Slobodan approximate maximum matching set cover hypergraph matching PRAM massively parallel computation The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there are two standard guarantees: an O(log Δ)-approximation (where Δ is the maximum set size) and an O(f)-approximation (where f is the maximum number of sets containing any given element). In this paper, we introduce a new, surprisingly simple, model-independent approach to solving SetCover in unweighted graphs. We obtain multiple improved algorithms in the MPC and CRCW PRAM models. First, in the MPC model with sublinear space per machine, our algorithms can compute an O(f) approximation to SetCover in Ô(√{log Δ} + log f) rounds and a O(log Δ) approximation in O(log^{3/2} n) rounds. Moreover, in the PRAM model, we give a O(f) approximate algorithm using linear work and O(log n) depth. All these bounds improve the existing round complexity/depth bounds by a log^{Ω(1)} n factor. Moreover, our approach leads to many other new algorithms, including improved algorithms for the HypergraphMatching problem in the MPC model, as well as simpler SetCover algorithms that match the existing bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laxman Dhulipala and Michael Dinitz and Jakub Łącki and Slobodan Mitrović 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.19 urn:nbn:de:0030-drops-212453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode