Streaming Algorithms for the $k$-Submodular Cover Problem

Abstract

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 $\ddot{I}„$. For this problem, we design a bicriteria algorithm with a cost at most $O(1/\hat{I}\mu )$ times the optimal value, while the utility is at least $(1-\hat{I}\mu )\ddot{I}„/r$, where $r$ depends on the monotonicity of $g$.