Improved Approximation Algorithms for K-Submodular Maximization Under a Knapsack Constraint

We investigate the problem of $k$-submodular maximization under a knapsack constraint over the ground set of size $n$. This problem finds many applications in various fields such as multi-topic propagation, multi-sensor placement, cooperative games, etc. However, existing algorithms for the studied problem face challenges in practice as the size of instances increases in practical applications. This paper introduces three deterministic and approximation algorithms for the problem that significantly improve both the approximation ratio and query complexity of existing practical algorithms.Our first algorithm, $\FA$, returns an approximation ratio of $1/10$ within $O(nk)$ query complexity. The second one, $\IFA$, improves the approximation ratio to $1/4-\epsilon$ in $O(nk/\epsilon)$ queries. The last one $\IFAP$ upgrades the approximation ratio to $1/3-\epsilon$ in $O(nk\log(1/\epsilon)/\epsilon)$ query complexity. Our algorithms are the first ones that provide constant approximation ratios within only $O(nk)$ query complexity, and the novel idea to achieve results lies in two aspects: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these ones with $O(nk)$ queries, (2) applying algorithmic frameworks that combine the solution of the first algorithm and greedy threshold method to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed ones with several experiments in some instances: Influence Maximization, Information Coverage Maximization, and Sensor Placement for the problem. The results confirm that our algorithms not only ensure theoretical quality as the cutting edge techniques including streaming and non-streaming algorithms but also significantly reduce the number of queries