Set Cover in Sub-linear Time

Set Cover in Sub-linear Time

© Copyright 2018 by SIAM. We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of m sets over n elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight query complexities. On one...

Full description

Bibliographic Details
Main Authors: Indyk, Piotr, Mahabadi, Sepideh, Rubinfeld, Ronitt, Vakilian, Ali, Yodpinyanee, Anak
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Book
Language:English
Published: Society for Industrial and Applied Mathematics 2021
Online Access:https://hdl.handle.net/1721.1/137642

Internet

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

Similar Items