  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\neq j}
\frac{c_i(e)}{c_j(e)}$ and $\epsilon, \alpha$ are fixed inputs.
