Improved Local Computation Algorithm for Set Cover via Sparsification

Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld +1

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, t…