Streaming algorithms for Budgeted $k$-Submodular Maximization problem

Abstract

Stimulated by practical applications arising from viral marketing. This paper investigates a novel Budgeted $k$-Submodular Maximization problem defined as follows: Given a finite set $V$, a budget $B$ and a $k$-submodular function $f:(k+1{)}^V\mapsto {\mathbb{R}}_{+}$, the problem asks to find a solution $\s=(S_1, S_2, \ldots, S_k)$, each element $e\in V$ has a cost $c_i(e)$ to be put into $i$-th set $S_i$, with the total cost of $s$ does not exceed $B$ so that $f(\s)$ is maximized. To address this problem, we propose two streaming algorithms that provide approximation guarantees for the problem. In particular, in the case of each element $e$ has the same cost for all $i$-th sets, we propose a deterministic streaming algorithm which provides an approximation ratio of $\frac{1}{4}-\epsilon$ when $f$ is monotone and $\frac{1}{5}-\epsilon$ when $f$ is non-monotone. For the general case, we propose a random streaming algorithm that provides an approximation ratio of $\min \{\frac{\alpha }{2},\frac{(1-\alpha )k}{(1+\beta )k-\beta }\}-\epsilon$ when $f$ is monotone and $\min \{\frac{\alpha }{2},\frac{(1-\alpha )k}{(1+2\beta )k-2\beta }\}-\epsilon$ when $f$ is non-monotone in expectation, where $\beta ={\max }_{e\in V,i,j\in [k],i\ne j}\frac{c_i(e)}{c_j(e)}$ and $\epsilon ,\alpha$ are fixed inputs.

There are some results of the article that need to be corrected