The problem of non-monotone $k$-submodular maximization under a knapsack
constraint ($\kSMK$) over the ground set size $n$ has been raised in many
applications in machine learning, such as data summarization, information
propagation, etc. However, existing algorithms for the problem are facing
questioning of how to overcome the non-monotone case and how to fast return a
good solution in case of the big size of data. This paper introduces two
deterministic approximation algorithms for the problem that competitively
improve the query complexity of existing algorithms.
Our first algorithm, $\LAA$, returns an approximation ratio of $1/19$ within
$O(nk)$ query complexity. The second one, $\RLA$, improves the approximation
ratio to $1/5-\epsilon$ in $O(nk)$ queries, where $\epsilon$ is an input
parameter.
Our algorithms are the first ones that provide constant approximation ratios
within only $O(nk)$ query complexity for the non-monotone objective. They,
therefore, need fewer the number of queries than state-of-the-the-art ones by a
factor of $\Omega(\log n)$.
Besides the theoretical analysis, we have evaluated our proposed ones with
several experiments in some instances: Influence Maximization and Sensor
Placement for the problem. The results confirm that our algorithms ensure
theoretical quality as the cutting-edge techniques and significantly reduce the
number of queries.

提出了两个确定性近似算法来解决非单调 k - 次模极大化问题，其在查询复杂度仅为 O (nk) 的情况下提供了常数近似比率，比现有算法少使用了 Omega (log n) 数量的查询。

非单调 $k$- 次模最大化问题的鲁棒近似算法在背包约束下

Robust Approximation Algorithms for Non-monotone $k$-Submodular  Maximization under a Knapsack Constraint

Submodular maximization has found extensive applications in various domains
within the field of artificial intelligence, including but not limited to
machine learning, computer vision, and natural language processing. With the
increasing size of datasets in these domains, there is a pressing need to
develop efficient and parallelizable algorithms for submodular maximization.
One measure of the parallelizability of a submodular maximization algorithm is
its adaptive complexity, which indicates the number of sequential rounds where
a polynomial number of queries to the objective function can be executed in
parallel. In this paper, we study the problem of non-monotone submodular
maximization subject to a knapsack constraint, and propose the first
combinatorial algorithm achieving an $(8+\epsilon)$-approximation under
$\mathcal{O}(\log n)$ adaptive complexity, which is \textit{optimal} up to a
factor of $\mathcal{O}(\log\log n)$. Moreover, we also propose the first
algorithm with both provable approximation ratio and sublinear adaptive
complexity for the problem of non-monotone submodular maximization subject to a
$k$-system constraint. As a by-product, we show that our two algorithms can
also be applied to the special case of submodular maximization subject to a
cardinality constraint, and achieve performance bounds comparable with those of
state-of-the-art algorithms. Finally, the effectiveness of our approach is
demonstrated by extensive experiments on real-world applications.

非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近