Sepideh Mahabadi
Set Cover in Sub-linear Time

Abstract: Given acacess to a collection of $m$ sets over a ground set
of $n$ elements, the classic set cover problem asks for the minimum
number of sets in the collection that cover all the elements. We study
this problem from the perspective of sub-linear algorithms, where the
input can be accessed by querying either the ith element contained in
a set, or the jth set containing an element. In this work, we present
sub-linear algorithms for the set cover problem and show that they
achieve almost tight query complexities.


This is a joint work with Piotr Indyk, Ronitt Rubinfeld, Ali
Vakilian, and Anak Yodpinyanee.