Abstract 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 P=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 -constraint scalarization approach is introduced, demonstrating enhanced efficiency in the numerical tests.
Könen et al. (Fri,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: