Algorithms with performance guarantees (Agape)

Project of Pole 2 Combinatorial Optimization , algorithms

The field of "algorithms with performance guarantees" brings together many scientific skills, from Operational Research and Theoretical Computing: algorithms, complexity theory, mathematical programming, discrete mathematics and combinatorics.

As a scientific field, "algorithms with performance guarantees" draws its scientific inspiration, its problems and its motivations from Operational Research, Combinatorial Optimization and Theoretical Computer Science, and gives to these scientific domains new concepts and powerful tools for analysis and solution of hard problems.

The AGaPe project develops four main axes:

   1. Approximation of NP-complete problems, a key area of ​​the scientific activity for project members for many years. The work in this domain concerns both the polynomial approximation (which includes more recent approaches such as the multi-criteria approximation and the robustness), the moderately exponential approximation (domain initiated by the members of the project) and the parameterized approximation;

   2. Exact solution of NP-complete problems and complexity;

   3. Dynamic optimization models for combinatorial problems (online algorithmics, reoptimization and probabilistic combinatorial optimization);

   4. Algorithmic games and combinatorial optimization.