Scholarlink

<p>This paper addresses the <i>output-sensitive</i> 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\textbf{P}=\textbf{N P}\)</EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> </InlineEquation>-constraint scalarization approach is introduced, demonstrating enhanced efficiency in the numerical tests.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Output-sensitive complexity of multi-objective integer network flow problems

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月23日

查看全文
  • David Könen,
  • Michael Stiglmayr

摘要

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 \(\textbf{P}=\textbf{N P}\) . 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 \(\varepsilon \) -constraint scalarization approach is introduced, demonstrating enhanced efficiency in the numerical tests.