Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint
Canh V. Pham, Dung K. T. Ha, Huan X. Hoang, Tan D. Tran · 2022 IEEE 9th International Conference on Data Science and Advanced Analytics (DSAA) · 2022
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 constant-approximation 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 state-of-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.