Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908385588281344 |
|---|---|
| author | Könen, David Stiglmayr, Michael |
| author_facet | Könen, David Stiglmayr, Michael |
| contents | This paper addresses the output-sensitive complexity for linear multi-objective integer minimum cost flow (MOIMCF) problems and provides insights about the time complexity for enumerating all supported nondominated vectors. The paper shows that there can not exist an output-polynomial time algorithm for the enumeration of all supported nondominated vectors that determine the vectors in an ordered way in the outcome space unless NP = P. Moreover, novel methods for identifying supported nondominated vectors in bi-objective minimum cost flow (BOIMCF) problems are proposed, accompanied by a numerical comparison between decision- and objective-space methods. A novel, equivalent and more compact formulation of the minimum cost flow ILP formulation used in the e-constrained-scalarization approach is introduced, demonstrating enhanced efficiency in the numerical tests |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01786 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems Könen, David Stiglmayr, Michael Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics G.2.1; G.2.2 This paper addresses the output-sensitive complexity for linear multi-objective integer minimum cost flow (MOIMCF) problems and provides insights about the time complexity for enumerating all supported nondominated vectors. The paper shows that there can not exist an output-polynomial time algorithm for the enumeration of all supported nondominated vectors that determine the vectors in an ordered way in the outcome space unless NP = P. Moreover, novel methods for identifying supported nondominated vectors in bi-objective minimum cost flow (BOIMCF) problems are proposed, accompanied by a numerical comparison between decision- and objective-space methods. A novel, equivalent and more compact formulation of the minimum cost flow ILP formulation used in the e-constrained-scalarization approach is introduced, demonstrating enhanced efficiency in the numerical tests |
| title | Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2312.01786 |