Complexity And Approximability Of Multiobjective Combinatorial Optimization Problems

The purpose of this task is to provide theoretical foundations for tasks 3, 4, and 5 by studying the complexity and approximability of problems (P1) and (P2) defined as follows:
(P1): finding the set of efficient or Pareto optimal solutions
(P2): determining a best compromise solution among the set of efficient solutions

Subtask 2.1 Complexity and approximability of the Pareto set
Concerning (P1), the main objective is to complement and unify existing results. The first question is related to intractability, i.e. the fact that the set of efficient solutions may have, in the worst case, an exponential size. Most classical combinatorial optimization problems are intractable in this sense. Intuitively, intractability results from the coexistence of very large and very small values in the instance, which is not a frequent situation in practice. Finding bounds on the size of the efficient set for a given instance is thus interesting and useful when designing an exact algorithm for determining the efficient set (task 3). Once a problem is proved intractable, it is interesting, from the computational viewpoint, to look for an approximation of the efficient set. A main goal of this task is to make progress in the study of the approximability of different combinatorial optimization problems. A first idea is to try to adapt to the multiobjective case classical algorithmic tools that proved fruitful in single objective approximation, for example local search and greedy strategies as done in [ABG04] and [ABGM05] or randomized rounding. Another idea that also takes advantage of existing algorithms for single objective problems consists in generating good tradeoff solutions from p initial solutions, each of these corresponding to approximate optimal solutions for each objective fj, j = 1,,p. This approach was successfully applied on a biobjective scheduling problem by Stein and Wein [SW97] and also on biobjective max cut problem [ABG06]. Generalizing such scattered results is a main objective. At this point it should be pointed out that extending single objective approximation techniques to the multiobjective case is not straightforward. This is mainly due to the fact that in the single objective case we aim at approximating one solution the optimal one whereas in the multiobjective case, we aim at approximating a whole set of solutions the Pareto set. Some of these approximation algorithms, in particular fptas and ptas, but also maybe other ones, can serve as useful starting points to design practically efficient algorithms for approximating the Pareto set (task 4).

Subtask 2.2 Complexity and approximability of best compromise solution
In general, problem (P2) is NP-hard for any interesting aggregation function (min-max, min-max regret, Tchebychev, OWA, Choquet) and for any combinatorial optimization problem (shortest path, minimum spanning tree, knapsack,). In some cases, however, (P2) is polynomial (e.g., min-max and min-max regret for min cut [ABV08], min-max and min-max regret for 1-median on trees [KY97]). At this level, our purpose is to complement these complexity results for all aggregation functions. Regarding approximability, we initiated quite recently the study of the min-max and min-max regret aggregation functions [ABV07]. However, no result is known for the other aggregation functions. Therefore, we plan to first study approximability for Tchebychev (which can be seen as a weighted extension of min-max regret) and then to other aggregation functions. Quite generally in this study, proving the existence of fptas or ptas for some combinatorial optimization problems is of primary importance if we wish to design efficient algorithms (task 5).