Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Authors Yingli Ran, Zhao Zhang, Shaojie Tang

Publication date 9 August 2021

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

f c o l o n 2^{V} i g h t a r r o w m a t h b b Z^{+}

, a linear cost function

c : V i g h t a r r o w m a t h b b R^{+}

, and an integer

k l e q f (V)

, the goal is to find a subset

A s u b s e t e q V

with the minimum cost such that

f (A) g e q 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 (f r a c l o g k m l o g k (l o g m + l o g l o g m k) v a r e p s i l o n^{4})

adaptive rounds, and it achieves an approximation ratio of

f r a c H (m i n D e l t a, k) 1 - 5 v a r e p s i l o n

with probability at least

1 - 3 v a r e p s i l o n

, where

D e l t a = m a x_{v i n V} f (v)

,

H (c d o t)

is the Harmonic number,

m = | V |

, and

v a r e p s i l o n

is a constant in

(0, f r a c 15)

.

This page was built for publication: Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374885)