Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint

This paper proposes two fast streaming algorithms for the problem of k-submodular maximization over the ground set of n elements under the knapsack constraint which is important and popular in combinatorial optimization and machine learning. Our algorithms are the first ones that provide constantapproximation ratios within O(nk) query complexity. The first algorithm is a single-pass streaming algorithm that returns a 1/10-approximation solution, the second one is a multi-pass streaming algorithm and improves the approximation ratio to nearly 1/4. Although these ratios are simply near to the stateof-the-art algorithms yet the number of queries can diminish by a large factor. We further investigate the performance of our algorithms by directing several experiments on instances of the issue: Influence Maximization and Sensor Placement. The outcomes confirm that our algorithms not only methodology in the quality arrangement of the cutting edge techniques including streaming and non-streaming algorithms yet in addition significantly reduce the number of queries.