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

• 成果类型: Article
• 署名作者: Mizutani, Ryuhei; Yoshida, Yuki
• 署名单位: Keio University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02327-3
• 发表日期: 2026-03
• 页码: 709-756
• 关键词: submodular functions

摘要

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.