In this work, we consider the Minimum Cost Submodular Cover ( \(\textsf{MCSC}\) ) problem over a ground set of size n, which aims at finding a subset with the minimal cost required such that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of artificial intelligence and combinatorial optimization, such as spreading and detecting information in social networks, data summuraization, recommendation systems, etc. However, the best approximation algorithm for the problem requires an expensive query complexity of \(O(n^2)\) that may become infeasible for some real applications with a massive size of data. To address this issue, we propose a bicriteria approximation algorithm that keeps the performance guarantees but significantly reduces the required number of queries and running time than the cutting-edge algorithm. In particular, our algorithm returns a \(\big ((1+\epsilon )(1+\log (1/\delta )), 1-\delta \big )\) -bicriteria ratio and takes \(O(n\log n)\) query complexity, where \(\epsilon , \delta >0\) are constant parameters. Besides the theoretical analysis, we conduct extensive experiments on two applications: Twitter feed summarization threshold and threshold influence in social networks. The results demonstrate that our algorithm outperforms the state-of-the-art regarding solution quality and query complexity.
