.png){kind=icon}
返回
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}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文研究了线性多目标最小费用整数流问题的输出敏感复杂度，为枚举所有支持非支配向量的时间复杂度提供了见解。研究表明，除非$\textbf{P}=\textbf{N P}$，否则不存在输出多项式时间算法来枚举所有确定结果空间中按词典序排列的支持非支配向量。此外，提出了用于识别双目标最小费用整数流问题中支持非支配向量的新方法，并辅以决策空间与目标空间方法的数值比较。介绍了一种新颖、等价且更紧凑的最小费用流ILP公式化方法，用于$\varepsilon$约束标量化方法，在数值测试中显示出更高的效率。
Keyword:
Minimum cost flow
Multi-objective integer linear programming
Multi-objective network flow
Complexity theory
Output-sensitive
Weakly supported
Output-polynomial algorithm
