Discrete representation of the non-dominated set for multi-objective optimization problems using kernels

We first establish some general properties on ε-kernels. Then, for the bi-objective case, we propose some generic algorithms computing in polynomial time either an ε-kernel of small size or, for a fixed size k, an ε-kernel with a nearly optimal approximation ratio 1+ɛ. For more than two objectives, we show that ε-kernels do not necessarily exist but that (ε, ε′)-kernels with ɛ′≤1+ɛ−1 always exist. Nevertheless, we show that the size of a smallest (ε, ε′)-kernel can be very far from the size of a smallest ε-Pareto set.