Sepideh Mahabadi, Columbia University

Abstract

Given access 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.

More specifically, on the one hand, we show an algorithm that returns an $alpha$-approximate cover using $tilde O(m(n/k)^{1/(alpha-1)} + nk)$ queries to the input, where $k$ denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of $k$, the required number of queries is $tilde Omega(m(n/k)^{1/(2alpha)})$. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require $Omega(nk)$ queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter $k$. On the other hand, we show that this bound is not optimal for larger values of the parameter $k$, as there exists a $(1+eps)$-approximation algorithm with $tilde O(mn/keps^2)$ queries. We show that this bound is also essentially tight by establishing a lower bound of $tilde Omega(mn/k)$.

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