Biobjective optimization with M-convex functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908840158560256 |
|---|---|
| author | Fukuda, Ellen H. Iwata, Satoru Nakagawa, Itsuki |
| author_facet | Fukuda, Ellen H. Iwata, Satoru Nakagawa, Itsuki |
| contents | 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$^\natural$-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$^\natural$-convex function is M-convex. Additionally, we present a polynomial-time method for biobjective optimization problems that combine M$^\natural$-convex function minimization with lexicographic optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23423 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Biobjective optimization with M-convex functions Fukuda, Ellen H. Iwata, Satoru Nakagawa, Itsuki Optimization and Control 52B40, 90C27, 90C29 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$^\natural$-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$^\natural$-convex function is M-convex. Additionally, we present a polynomial-time method for biobjective optimization problems that combine M$^\natural$-convex function minimization with lexicographic optimization. |
| title | Biobjective optimization with M-convex functions |
| topic | Optimization and Control 52B40, 90C27, 90C29 |
| url | https://arxiv.org/abs/2507.23423 |