Fast Bicriteria Approximation Algorithm for Minimum Cost Submodular Cover Problem

This paper studies the Minimum Cost Submodular Cover ( \(\textsf{MCSC}\) ) problem over the ground set of size n, which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The issue has recently attracted a lot of attention due to its applications in various domains of artificial intelligence and combination optimization. However, the best approximation algorithm for the problem requires an expensive query complexity of \(O(n^2)\) that may become infeasible for some applications with large data. In this work, we propose a bicriteria approximation algorithm that keeps the performance guarantees of the state-of-the-art ones but reduces the required number of queries to \(O(n\log n)\) . Besides the theoretical, the experiment results on two applications, Twitter feed threshold summarization, and threshold influence in social networks, further show the superiority of our algorithm with the state-of-the-art in terms of both solution quality and query complexity.