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