Treffer: An output-polynomial time algorithm to determine all supported efficient solutions for multi-objective integer network flow problems

Title:
An output-polynomial time algorithm to determine all supported efficient solutions for multi-objective integer network flow problems
Authors:
David Könen, Michael Stiglmayr
Source:
Discrete Applied Mathematics. 376:1-14
Publication Status:
Preprint
Publisher Information:
Elsevier BV, 2025.
Publication Year:
2025
Subject Terms:
Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Optimization and Control
Document Type:
Fachzeitschrift Article
Language:
English
ISSN:
0166-218X
DOI:
10.1016/j.dam.2025.06.001
DOI:
10.48550/arxiv.2305.12867
Access URL:
http://arxiv.org/abs/2305.12867
Rights:
CC BY
CC BY NC ND
Accession Number:
edsair.doi.dedup.....5570bec4b9baf255f5890eb171ef6d9f
Database:
OpenAIRE

Weitere Informationen

This paper addresses the problem of enumerating all supported efficient solutions for a linear multi-objective integer minimum cost flow problem (MOIMCF). It derives an output-polynomial time algorithm to determine all supported efficient solutions for MOIMCF problems. This is the first approach to solve this general problem in output-polynomial time. Moreover, we prove that the existence of an output-polynomial time algorithm to determine all weakly supported nondominated vectors (or all weakly supported efficient solutions) for a MOIMCF problem with a fixed number of d >= 3 objectives can be excluded unless P = NP.