Biobjective optimization with M-convex functions

• 成果类型: Article; Early Access
• 署名作者: Fukuda, Ellen H.; Iwata, Satoru; Nakagawa, Itsuki
• 署名单位: Kyoto University; University of Tokyo; Hokkaido University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02393-7
• 发表日期: 2026-08-12
• 关键词: biobjective optimization; discrete convex functions; M-convex functions; Pareto optimality; VALUATED MATROID INTERSECTION; Efficient algorithms

摘要

In this paper, we deal with two ingredients that, as far as we know, have not been combined until now: multiobjective optimization and discrete convex analysis. First, we show that the entire Pareto optimal value set can be obtained in polynomial time for biobjective optimization problems with discrete convex functions, in particular, involving an M-#-convex function and a linear function with binary coefficients. We also observe that a more efficient algorithm can be obtained in the special case where the M-#-convex function is M-convex. Additionally, we present a polynomial-time method for biobjective optimization problems that combine M-#-convex function minimization with lexicographic optimization.