Program > By author > Jamain Florian

Most multicriteria combinatorial optimization problems admit families of instances for which the number of non-dominated points is exponential in the size of the instance. Thus, we cannot produce the full set of non-dominated points, we have to contend with an approximation of this set. The goal is to compute and give to a decision maker a set of solutions that represents as well as possible the different choices. A good representation is evaluated according to three main dimensions, the quality of the dominance, i.e. providing a good approximation, the stability, i.e. that does not include any redundancies, the cardinality, i.e. that does not contain too many points. The idea of the approximation is represented by the concept of an e-Pareto set, which is a set of solutions that approximately dominates every other solutions, i.e. such that for every solution S it contains a solution S' that is better within a factor (1+e) than S in all the objectives. Note that there may exist several e-Pareto sets, some of which can include some redundancies and some of which can have very small size and some others very large size.
It is shown by Papadimitriou and Yannakakis (2000) that for every classical multicriteria optimization problem an e-Pareto set of polynomial size always exists and moreover it can be computed in polynomial time if and only if the routine GAP associated can be solved in polynomial time. An interesting problem introduced by Vassilvitski and Yannakakis (2005) and continued by Diakonikolas and Yannakakis (2009) is the efficient construction of an e-Pareto set of size as small as possible. In this work, in order to obtain a good representation, we focus on the same issue but we want to obtain some particular e-Pareto sets called e-kernels that satisfy a property of stability. The points in an e-kernel have to be pairwise independent relatively to the (1+e)-dominance relation.

We show some general results about e-kernels and present a polynomial time algorithm to construct small e-kernels under some conditions for the bicriteria case. We show that an e-kernel does not always exist when the number of criteria is at least three.