Efficient Parallel Algorithm for Minimum Cost Submodular Cover Problem with Lower Adaptive Complexity.

In this paper, we study the Minimum Cost Submodular Cover (ℳ ) 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 problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a (1 − λ , (1 +) (1 + log 1 λ)) -bicriteria approximation solution within O (log n) adaptive complexity, where λ , are fixed parameters. Our algorithm requires O (n 2 log 2 n) query complexity, however, it can reduce to O (n log 3 n) instead while retaining a low adaptive complexity of O (log 2 n). Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem. [ABSTRACT FROM AUTHOR]