An Efficient Streaming Algorithm for the Submodular Cover Problem
We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESCStreaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large-scale graph cover problems.
This paper studies the streaming version of set cover.  In the model proposed here, the input consists of sets that cover a universe that arrive online in an arbitrary order, and an algorithm must find an approximately optimal solution using a single pass on the input while using sublinear memory.  The main result shows that if one is willing to compromise for a 1-\epsilon coverage of the universe, there is an algorithm that achieves (log n/\epsilon) approximation of the offline optimal solution.  Thus, the algorithm is 2/\epsilon factor of optimal, as the offline set cover problem cannot be approximated within a factor strictly better than log n.  In addition, the authors justify the relaxed version of set cover with a nice lower bound.  They show that obtaining a non-trivial approximation guarantee for the online set cover problem (i.e. without the 1-\epsilon relaxation) requires linear memory.
The problem studied is the min set cover where there is a family of sets that cover some universe and the goal is to find a family of sets of minimal size that covers at least Q elements in the universe.  It is well known that this problem is NP hard and that no polynomial time algorithm can obtain an approximation guarantee better than log n, under reasonable computational complexity assumptions.    In the streaming setting, defined in this paper for this problem for the first time, the goal is to solve the set cover problem using a single pass on the data using sublinear memory when the assumption is that sets arrive in an adversarial order.    Motivated by impossibility results for this problem, shown in this paper, the authors define the Streaming Bicriteria Submodular Cover (SBSC) problem where the goal is to obtain (1-\epsilon,delta) bi-criteria approximations, i.e. cover a (1-\epsilon) fraction of the universe using \delta factor of the minimum sets of the optimal solution.  The main result is a streaming algorithm in the model defined which covers a (1-\epsilon) fraction of universe using 2/\epsilon sets of the optimal solution.  The idea of the analysis is a refinement of the classic analysis of the greedy algorithm for set cover by Wolsey.  In particular, as the authors point out, if the greedy algorithm is stopped after covering 1-\epsilon of the universe, this implies that at most k*ln(1/\epsilon) sets are picked which gives a tight (1-\epsilon,ln(1/\epsilon)) bi criteria  offlne apx algorithm.    The authors essentially take this idea and turn it into a streaming algorithm by maintaining log n different solutions, each with a different threshold (in multiples of 2).  An element is then added to all the solutions in which its coverage passed the threshold of the solution.  At a high level, the idea of the algorithm is very similar to previous streaming algorithms for the dual max-k-cover problem.  The analysis however, introduces new ideas as discussed above.     In terms of applications, the authors give two nice applications of active set selection and graph set cover.  Both are problems studied in the past where it is quite reasonable to use a streaming algorithm.  The experiments are quite comprehensive, and are preformed on very large data sets (graphs with nearly a billion nodes and ~50 billon edges).  The algorithm was run against strong benchmarks, and seems to be competitive with the offline greedy algorithm which is optimal for this problem.  Overall, this is a nice paper. The paper introduces a new problem which is quite natural and does a great job in modeling given that the strict version of the problem does not yield non-trivial solutions.  The algorithms are similar to previous ones for related problems, but the ideas guiding the analysis are all new and interesting.  The applications are interesting and the experiments are solid.  In addition, the paper is well written and easy to follow.       Minor comments:  - In line 47, shouldn't the main result be 2/\epsilon (rather than 1/\epsilon) of the minimal number of sets?