Streaming Algorithms for Maximizing k-Submodular Functions with the Multi-knapsack Constraint

The problem of maximizing submodular functions with constraints has attracted widespread attention in the past few decades. In recent years, the extensions of submodular functions were studied, such as lattice submodular functions, diminishing return submodular (DR-submodular) functions and k-submodular functions. A k-submodular function is a generalization of a submodular function to k dimensions. Many machine learning problems can be cast as k-submodular maximization problems, for example, influence maximization with k kinds of topics and sensor placement with k kinds of sensors. Recently, the unprecedented growth in modern datasets makes it necessary to design streaming algorithms. This paper investigates the problem of maximizing a nonnegative normalized k-submodular function with the multi-knapsack constraint (also called the d-knapsack constraint) in the streaming model. To address this problem, we design an efficient streaming algorithm that runs in one pass, stores at most \(O\left( \frac{b\log b}{\varepsilon }\right) \) $O\left(\frac{blogb}{\epsilon }\right)$ elements and queries at most \(O\left( \frac{dk\log b}{\varepsilon }\right) \) $O\left(\frac{dklogb}{\epsilon }\right)$ per element where b is a constant after the normalization of the problem. This streaming algorithm also can achieve a \(\Big (\frac{1}{2(1+d)}-\varepsilon \Big )\) $(\frac{1}{2(1+d)}-\epsilon )$ -approximation when the objective function f is monotone and \(\Big (\frac{1}{3+2d}-\varepsilon \Big )\) $(\frac{1}{3+2d}-\epsilon )$ -approximation when the objective function f is non-monotone.