Maximizing k-submodular functions under budget constraint: applications and streaming algorithms

Motivated by the practical applications in solving plenty of important combinatorial optimization problems, this paper investigates the 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}_+$$ f : ( k + 1 ) V ↦ R + , the problem asks to find a solution $$\mathbf{s }=(S_1, S_2, \ldots , S_k) \in (k+1)^V $$ s = ( S 1 , S 2 , … , S k ) ∈ ( k + 1 ) V , in which an element $$e \in V$$ e ∈ V has a cost $$c_i(e)$$ c i ( e ) when added into the i-th set $$S_i$$ S i , with the total cost of $$\mathbf{s }$$ s that does not exceed B so that $$f(\mathbf{s })$$ f ( s ) is maximized. To address this problem, we propose two single pass streaming algorithms with approximation guarantees: one for the case that an element e has only one cost value when added to all i-th sets and one for the general case with different values of $$c_i(e)$$ c i ( e ) . We further investigate the performance of our algorithms in two applications of the problem, Influence Maximization with k topics and sensor placement of k types of measures. The experiment results indicate that our algorithms can return competitive results but require fewer the number of queries and running time than the state-of-the-art methods.