Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function f : 2(V) -> Z(+), a linear cost function c : V -> R+, and an integer k <= f(V), the goal is to find a subset A subset of V with the minimum cost such that f(A) >= k. The MinSMC can be found at the heart of many machine learning and data mining applications. In this paper, we design a parallel algorithm for the MinSMC that takes at most O(log(km) log k(logm+log log(mk))/epsilon(4)) adaptive rounds, and it achieves an approximation ratio of H(min{Delta,k})/1-5 epsilon with probability at least 1 - 3 epsilon, where Delta = max(v subset of V) f(v), H(center dot) is the Harmonic number, m = vertical bar V vertical bar, and epsilon is a constant in (0, 1/5).