Improved Local Computation Algorithm for Set Cover via Sparsification

We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most s and each element is contained in at most t sets, the algorithm reports whether a given set is in some fixed set cover whose expected size is O (log s ) times the minimum fractional set cover value. Our algorithm requires s O (log s ) t O (log s +log log t )) queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS’07] on the result of [Kuhn et al. , SODA’06], which leads to a query complexity of ( st ) O (log s · log t ). To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA’19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al. , FOCS’89]. However, our algorithm differs in the way that it never revokes its decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.

Authors

• Christoph Grunau
• Slobodan Mitrovic
• Ronitt Rubinfeld
• Ali Vakilian

Keywords

No keywords are indexed for this paper.