The Satisfactory Partition problem asks for deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [M. Gerber, D. Kobler,...

In the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0-1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations...

Min-max and min-max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min-max and min-max regret versions of some combinatorial optimization problems: shortest path,...

The goal of this thesis is to propose new general methods to get around the intractability of multi-objective optimization problems.First, we try to give some insight on this intractability by determining an, easily computable, upper bound on the number of nondominated points, knowing the number...

In this paper, we consider the problem of adaptive traffic control on single junctions with the three following objectives to be minimized: the total waiting time and the number of stops for private vehicles, and a public transport criterion. This problem being modeled as a multi-objective mixed...

This thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori...