Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Yingli Ran; Zhao Zhang; Shaojie Tang

Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Yingli Ran, Zhao Zhang, Shaojie Tang

Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3490-3502, 2022.

Abstract

In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function

$f\colon 2^V \rightarrow \mathbb{Z}^+$ , a linear cost function

$c: V\rightarrow \mathbb R^{+}$ , and an integer

$k\leq f(V)$ , the goal is to find a subset

$A\subseteq V$ with the minimum cost such that

$f(A)\geq 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))}{\varepsilon^4})$ adaptive rounds, and it achieves an approximation ratio of

$\frac{H(\min\{\Delta,k\})}{1-5\varepsilon}$ with probability at least

$1-3\varepsilon$ , where

$\Delta=\max_{v\in V}f(v)$ ,

$H(\cdot)$ is the Harmonic number,

$m=|V|$ , and

$\varepsilon$ is a constant in

$(0,\frac{1}{5})$ .

Cite this Paper

BibTeX


@InProceedings{pmlr-v178-ran22a,
  title = 	 {Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem},
  author =       {Ran, Yingli and Zhang, Zhao and Tang, Shaojie},
  booktitle = 	 {Proceedings of Thirty Fifth Conference on Learning Theory},
  pages = 	 {3490--3502},
  year = 	 {2022},
  editor = 	 {Loh, Po-Ling and Raginsky, Maxim},
  volume = 	 {178},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {02--05 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v178/ran22a/ran22a.pdf},
  url = 	 {https://proceedings.mlr.press/v178/ran22a.html},
  abstract = 	 {In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function $f\colon 2^V \rightarrow \mathbb{Z}^+$, a linear cost function $c: V\rightarrow \mathbb R^{+}$, and an integer $k\leq f(V)$, the goal is to find a subset $A\subseteq V$ with the minimum cost such that $f(A)\geq 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))}{\varepsilon^4})$ adaptive rounds, and it achieves an approximation ratio of $\frac{H(\min\{\Delta,k\})}{1-5\varepsilon}$ with probability at least  $1-3\varepsilon$, where $\Delta=\max_{v\in V}f(v)$, $H(\cdot)$ is the Harmonic number, $m=|V|$, and $\varepsilon$ is a constant in $(0,\frac{1}{5})$.}
}

Endnote

%0 Conference Paper
%T Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem
%A Yingli Ran
%A Zhao Zhang
%A Shaojie Tang
%B Proceedings of Thirty Fifth Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2022
%E Po-Ling Loh
%E Maxim Raginsky	
%F pmlr-v178-ran22a
%I PMLR
%P 3490--3502
%U https://proceedings.mlr.press/v178/ran22a.html
%V 178
%X In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function $f\colon 2^V \rightarrow \mathbb{Z}^+$, a linear cost function $c: V\rightarrow \mathbb R^{+}$, and an integer $k\leq f(V)$, the goal is to find a subset $A\subseteq V$ with the minimum cost such that $f(A)\geq 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))}{\varepsilon^4})$ adaptive rounds, and it achieves an approximation ratio of $\frac{H(\min\{\Delta,k\})}{1-5\varepsilon}$ with probability at least  $1-3\varepsilon$, where $\Delta=\max_{v\in V}f(v)$, $H(\cdot)$ is the Harmonic number, $m=|V|$, and $\varepsilon$ is a constant in $(0,\frac{1}{5})$.

APA


Ran, Y., Zhang, Z. & Tang, S.. (2022). Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3490-3502 Available from https://proceedings.mlr.press/v178/ran22a.html.

Related Material

Download PDF