.png){kind=icon}
.png){kind=icon}
Return
Output-sensitive complexity of multi-objective integer network flow problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-025-01376-2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses the output-sensitive complexity for linear multi-objective minimum cost integer flow problem, providing insights into the time complexity for enumerating all supported nondominated vectors. The paper shows that there cannot exist an output-polynomial time algorithm for the enumeration of all supported nondominated vectors that determine the vectors in an lexicographically ordered way in the outcome space unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{P}=\textbf{N P}$$\end{document}. Moreover, novel methods for identifying supported nondominated vectors in bi-objective minimum cost integer flow 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-constraint scalarization approach is introduced, demonstrating enhanced efficiency in the numerical tests.
Keywords:
Minimum cost flow
Multi-objective integer linear programming
Multi-objective network flow
Complexity theory
Output-sensitive
Weakly supported
Output-polynomial algorithm
Journal
J
IF:
1.1
Papers:
78
Citations:
0