Scholarlink

<p>A fundamental result in combinatorial optimization is that submodular functions can be minimized in polynomial-time. In this paper, we consider the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. In this paper, we provide two weakly polynomial-time algorithms to minimize 2/3-submodular functions. We also present a min-max theorem for 2/3-submodular functions, which extends the celebrated min-max theorem for submodular functions.</p>

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

Weakly polynomial-time algorithms to minimize 2/3-submodular functions

  • 期刊论文

  • 发表日期：

    2026年1月26日

查看全文
  • Ryuhei Mizutani,
  • Yuki Yoshida

摘要

A fundamental result in combinatorial optimization is that submodular functions can be minimized in polynomial-time. In this paper, we consider the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. In this paper, we provide two weakly polynomial-time algorithms to minimize 2/3-submodular functions. We also present a min-max theorem for 2/3-submodular functions, which extends the celebrated min-max theorem for submodular functions.