This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size n subject to a knapsack constraint, DLA and RLA. DLA is a deterministic algorithm that provides an approximation factor of nearly 6 while RLA is a randomized algorithm with an approximation factor of nearly 4. Both run in linear query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.

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.