Seminars & Colloquia Calendar

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.