arbiter
JournalsPricingAccount

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

David Könen & Michael Stiglmayr

Journal of Combinatorial Optimization2026https://doi.org/10.1007/s10878-025-01376-2article
AJG 2
Weight
0.50

What the paper says

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.

Open paper page →

Cite this paper

https://doi.org/https://doi.org/10.1007/s10878-025-01376-2

Or copy a formatted citation

@article{david2026,
  title        = {{Output-sensitive complexity of multi-objective integer network flow problems}},
  author       = {David Könen & Michael Stiglmayr},
  journal      = {Journal of Combinatorial Optimization},
  year         = {2026},
  doi          = {https://doi.org/https://doi.org/10.1007/s10878-025-01376-2},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

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

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.