Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint
- Resource Type
- Conference
- Authors
- Pham, Canh V.; Ha, Dung K.T.; Hoang, Huan X.; Tran, Tan D.
- Source
- 2022 IEEE 9th International Conference on Data Science and Advanced Analytics (DSAA) Data Science and Advanced Analytics (DSAA), 2022 IEEE 9th International Conference on. :1-10 Oct, 2022
- Subject
- Bioengineering
Communication, Networking and Broadcast Technologies
Computing and Processing
Signal Processing and Analysis
Sensor placement
Machine learning algorithms
Costs
Machine learning
Data science
Approximation algorithms
Linear programming
Approximation algorithm
k-submodular maximization
knapsack constraint
streaming algorithm
- Language
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.