Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Abstract

In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function $f:2^V\to {\mathbb{Z}}^{+}$, a linear cost function $c:V\to {\mathbb{R}}^{+}$, and an integer $k\le f(V)$, the goal is to find a subset $A\subseteq V$ with the minimum cost such that $f(A)\ge 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(\frac{\log km\log k(\log m+\log \log mk)}{{\epsilon }^4})$ adaptive rounds, and it achieves an approximation ratio of $\frac{H(\min \{\Delta ,k\})}{1-5\epsilon }$ with probability at least $1-3\epsilon$, where $\Delta ={\max }_{v\in V}f(v)$, $H(\cdot )$ is the Harmonic number, $m=|V|$, and $\epsilon$ is a constant in $(0,\frac{1}{5})$.

arXiv commentOur paper has been accepted to 35th Annual Conference on Learning Theory