Nos tutelles

CNRS Dauphine PSL *


Accueil > Projets

Project « Algorithms with performance guarantees (AGaPe) »

publié le , mis à jour le

The area of the design of algorithms with performance guarantees lies in the interface of several research domains, mainly in the interface of Operations Research (in particular of Combinatorial Optimization) of and Theoretical Computer Science. This area brings together several disciplines as theory of algorithms, complexity theory, mathematical programming, discrete mathematics, combinatorics, etc.

Four main axes are developed within the AGaPe project :

  • 1. Approximation of NP-hard problems. This axis has been the seminal axis of the re-search activities of the AGaPe project since its establishment in the LAMSADE labora-tory at 1992. Research here includes both polynomial time approximation (including recent approaches such as multicriteria approximation, labelled problems and ro-bustness) and moderately exponential time approximation, domain recently initiated by members of the AGaPe project, as well as the parametrized approximation ;
  • 2. Worst case complexity of exact algorithms for NP-hard problems with provably upper running time bounds ;
  • 3. Optimization models dealing with dynamic problem-instances (on-line algorithms, reoptimization and probabilistic combinatorial optimization) ;
  • 4. Algorithmic game theory and combinatorial optimization.

Project members :

  • Permanent members : Cristina Bazgan, Marc Demange, Aristotelis Giannakos, Laurent Gourvès, Eunjung Kim, Jérôme Monnot, Cécile Murat, Vangelis Th. Paschos, Bernard Ries, Florian Sikora.
  • Post-Docs : F. Foucaud, D Sasaki, G. Stamoulis.
  • ATER, PhD students : E. Bonnet, F. Jamain, L. Tlilane.