TY - JOUR

T1 - Approximating multiobjective optimization problems

T2 - How exact can you be?

AU - Bazgan, Cristina

AU - Herzel, Arne

AU - Ruzika, Stefan

AU - Thielen, Clemens

AU - Vanderpooten, Daniel

N1 - Publisher Copyright:
© The Author(s) 2023.

PY - 2024/8

Y1 - 2024/8

N2 - It is well known that, under very weak assumptions, multiobjective optimization problems admit (1+ε,⋯,1+ε)-approximation sets (also called ε-Pareto sets) of polynomial cardinality (in the size of the instance and in 1ε). While an approximation guarantee of 1+ε for any ε>0 is the best one can expect for singleobjective problems (apart from solving the problem to optimality), even better approximation guarantees than (1+ε,⋯,1+ε) can be considered in the multiobjective case since the approximation might be exact in some of the objectives. Hence, in this paper, we consider partially exact approximation sets that require to approximate each feasible solution exactly, i.e., with an approximation guarantee of 1, in some of the objectives while still obtaining a guarantee of 1+ε in all others. We characterize the types of polynomial-cardinality, partially exact approximation sets that are guaranteed to exist for general multiobjective optimization problems. Moreover, we study minimum-cardinality partially exact approximation sets concerning (weak) efficiency of the contained solutions and relate their cardinalities to the minimum cardinality of a (1+ε,⋯,1+ε)-approximation set.

AB - It is well known that, under very weak assumptions, multiobjective optimization problems admit (1+ε,⋯,1+ε)-approximation sets (also called ε-Pareto sets) of polynomial cardinality (in the size of the instance and in 1ε). While an approximation guarantee of 1+ε for any ε>0 is the best one can expect for singleobjective problems (apart from solving the problem to optimality), even better approximation guarantees than (1+ε,⋯,1+ε) can be considered in the multiobjective case since the approximation might be exact in some of the objectives. Hence, in this paper, we consider partially exact approximation sets that require to approximate each feasible solution exactly, i.e., with an approximation guarantee of 1, in some of the objectives while still obtaining a guarantee of 1+ε in all others. We characterize the types of polynomial-cardinality, partially exact approximation sets that are guaranteed to exist for general multiobjective optimization problems. Moreover, we study minimum-cardinality partially exact approximation sets concerning (weak) efficiency of the contained solutions and relate their cardinalities to the minimum cardinality of a (1+ε,⋯,1+ε)-approximation set.

KW - Approximation

KW - Efficient set

KW - Intractability

KW - Multiobjective optimization

UR - http://www.scopus.com/inward/record.url?scp=85172667201&partnerID=8YFLogxK

U2 - 10.1007/s00186-023-00836-x

DO - 10.1007/s00186-023-00836-x

M3 - Article

AN - SCOPUS:85172667201

SN - 1432-2994

VL - 100

SP - 5

EP - 25

JO - Mathematical Methods of Operations Research

JF - Mathematical Methods of Operations Research

IS - 1

ER -