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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On k-Submodular Function Optimization

  • Qiufen Ni,
  • Zhongzheng Tang

摘要

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.