In this paper, we present a comprehensive study of the regularized \(\gamma \) -weakly submodular maximization problem, where the objective \(f=g-c\) is formulated as the difference between a non-negative \(\gamma \) -weakly submodular function and a non-negative modular function. This problem has garnered significant attention in recent years. While prior works have focused primarily on monotone functions g, we extend our investigation to the non-monotone case. We contribute by presenting an efficient algorithm for this problem, accompanied by a strong approximation guarantee.

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

Regularized Non-monotone \(\gamma \) -weakly Submodular Maximization

  • Zhicheng Liu,
  • Yufeng Yang,
  • Chunlin Hao,
  • Wenqing Xu

摘要

In this paper, we present a comprehensive study of the regularized \(\gamma \) -weakly submodular maximization problem, where the objective \(f=g-c\) is formulated as the difference between a non-negative \(\gamma \) -weakly submodular function and a non-negative modular function. This problem has garnered significant attention in recent years. While prior works have focused primarily on monotone functions g, we extend our investigation to the non-monotone case. We contribute by presenting an efficient algorithm for this problem, accompanied by a strong approximation guarantee.