Improved local computation algorithm for set cover via sparsification

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 fracti...

Full description

Bibliographic Details
Main Authors: Mitrović, Slobodan, Rubinfeld, Ronitt
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Society for Industrial and Applied Mathematics 2021
Online Access:https://hdl.handle.net/1721.1/130417

Internet

https://hdl.handle.net/1721.1/130417

Similar Items