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) 数量的查询。