Partenaires

CNRS
Nom tutelle 1 Nom tutelle 2
Nom tutelle 3 Nom tutelle 4


Search


Home > Edito

Description of the Project

by aymeric - published on , updated on

Description of the Project


The aim of the project is to propose a new global approach dealing with trading off between running time and precision of algorithms solving combinatorial optimization problems. This requires the de-velopment of novel theoretical frameworks that allow us to go beyond the drawbacks of the classical dichotomy polynomial/exponential time, in order to achieve two goals: bringing, on a theoretical viewpoint, new elements for understanding hard combinatorial optimization problems and their solution, and providing, on a practical viewpoint, efficient methods satisfying both running time and precision requirements. To achieve these aims, the project consists of the development of three complementary lines of research:

  • Exact solution of hard problems
  • Coping with inapproximability: moderately exponential approximation
  • Solving massive data sets by low complexity algorithms (very fast approximation).

The project will develop these three approaches. They all contribute to better understand the intrin-sic difficulty of combinatorial optimization problems solution, by suggesting a broader study of the relations between modes of solution of the problems (exact, approximate) and computation time, a central issue to the whole area of algorithmic theory. The basic question to be answered is: what is possible/impossible to do given a computation time bound?

Research within the TODO project will be carried out along five main research tasks:

  1. Exact computation with provably time complexity upper bounds (task’s manager: Bruno Escoffier)
  2. Coping with polynomial inapproximability: moderately exponential approximation (task’s manager: Vangelis Th. Paschos)
  3. Very fast approximation (task’s manager: Evripidis Bampis)
  4. Implementation of the algorithms (task’s manager: Christian Laforest)
  5. Midway and final workshops (task’s managers: Aristotelis Giannakos and Cécile Murat)

The project will be carried out by the following research laboratories:

  • LAMSADE (Université Paris-Dauphine), research team "Optimisation Combinatoire et Applications"
  • IBISC (Université d’Évry-Val d’Essonne), research team "Optimisation et Algorithmes" (OPAL)
  • LIMOS (Université d’Auvergne, Université Blaise Pascal, ISIMA, IFMA), research team "Recherche Opérationnelle et Aide à la Décision"
  • Department of Information Systems and Decision Science (ESSEC), research team "Decision Science"

Project’s coordinator is Vangelis Th. Paschos, Professor of Computer Science, LAMSADE, Université Paris-Dauphine. Local coordinators are:

  • Euripide Bampis for the IBISC’s team
  • Christian Laforest for the LIMOS’ team
  • Marc Demange for the ESSEC’s team