Streaming Algorithms for the $k$-Submodular Cover Problem

Given a natural number $k\ge 2$, we consider the $k$-submodular cover problem ($k$-SC). The objective is to find a minimum cost subset of a ground set $\mathcal{X}$ subject to the value of a $k$-submodular utility function being at least a certain predetermined value $τ$. For this problem, we design a bicriteria algorithm with a cost at most $O(1/ε)$ times the optimal value, while the utility is at least $(1-ε)τ/r$, where $r$ depends on the monotonicity of $g$.