On k-Submodular Function Optimization
摘要
A k-submodular function is a generalization of a submodular function to k disjoint subsets. The optimization problems for monotone or non-monotone k-submodular function with various constraints have attracted extensive research. Researchers propose optimization methods for k-submodular function maximization in two types: the combinatorial algorithms and the continuous extension algorithms. We synthesize the main approximation methods for the optimization problem on k-submodular function and their approximation theoretical guarantees in this paper. Additionally, we summarize the main approximation ratios for k-submodular function without constraint and with different constraints.