2024/12/02 by José Rui Figueira, Figueira, José Rui, Kathrin Klamroth +4
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2412.01465
openalex publication_date 2024/12/02 · openalex created_date 2024/12/05 · openalex updated_date 2026/07/28
Multi-objective unconstrained combinatorial optimization problems (MUCO) are in general hard to solve, i.e., the corresponding decision problem is NP-hard and the outcome set is intractable. In this paper we explore special cases of MUCO problems that are actually easy, i.e., solvable in polynomial time. More precisely, we show that MUCO problems with up to two ordinal objective functions plus one real-valued objective function are tractable, and that their complete nondominated set can be computed in polynomial time. For MUCO problems with one ordinal and a second ordinal or real-valued objective function we present an even more efficient algorithm that applies a greedy strategy multiple times.