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 ⊆ 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(log m+log log(mk⁾⁾ ) ε⁴ adaptive rounds, and it achieves an approximation ratio of ^H(min{∆,k}) with probability at least 1−5ε 1 − 3ε, where ∆ = max_v∈_V f(v), H(·) is the Harmonic number, m = |V |, and ε is a constant in (0, ¹₅ ).