Nos tutelles

CNRS Dauphine PSL *


Accueil > RECHERCHE > Pôles

Combinatorial Optimization, Algorithms

publié le , mis à jour le

Combinatorial Optimization addresses the full-range of theoretical questions raised, originally, by a particular type of real-life applications. The answers translate into algorithms the efficiency of which is measured by numerical experiments and in terms of complexity theory.

"Combinatorial Optimization, Algorithms" leads research based on the following projects :

AGaPe and Mathis have in common the study of NP-hard problems relaxations, where the relaxation covers instances structures (Mathis/AGaPe), feasible solutions set (Mathis), optimality of the given solution (AGaPe/Mathis), and the time taken to find it (AGaPe). The projects are also investigating generalizations of polynomial problems. Generalization covers optimality criteria (Multi-objective), optimizing criteria in concurrence (Game), dynamism of the data (Services), and reliability of the data (Mathis).

Links :

Applications :
Production, telecommunications, dynamic simulation models, Web Services, processing of multimedia data, Distributed Digital Music Archives and Libraries program, etc.

Key words :
mathematical programming (linear programming and integer linear programming, polyhedral combinatorics), polynomial and weakly exponential approximation (parametrized complexity, FPT algorithms), robustness (stochastic optimization , progressive instances, on-line algorithms, re-optimization), massive data optimization, simulation, supply chains, services.