Robust Approximation Algorithms for Non-monotone $k$-Submodular
  Maximization under a Knapsack Constraint
Dung T. K. Ha Canh V. Pham Tan D. Tran Huan X. Hoang
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.