Approximation geometrique structurelle pour l'algorithmique – SAGA

L’optimisation combinatoire trouve de nombreuses applications dans les problèmes de gestion de ressources notamment dans les compagnies de transport, dans la production industrielle ou dans la finance et le médical. Deux catégories principales émergent parmi les problèmes d’optimisation : les problèmes de recouvrement « covering » et les problèmes de « packing » avec de nombreuses applications dans le routage, la planification ou l’allocation de ressources.

Ces problèmes sont connus pour être NP-complet. De plus, il reste très difficile de fournir des solutions approchées. Par exemple, aucun algorithme ne peut fournir une solution approchée au problème de « set-cover » sans introduire un facteur multiplicatif logarithmique, de même, pour le problème des « independent set » un facteur polynomial apparaît lorsque l’on veut obtenir une solution approchée.

La prolifération des périphériques mobiles, sources massives données, et l’explosion des informations partagées sur le web ont rendu les données en entrée de ces problèmes de plus en plus volumineuses et complexes à analyser. De ce fait, les approches algorithmiques actuelles dépassent la limite de l’incalculable. Proposer de nouvelles solutions algorithmiques rapides, flexibles et garantissant une certaine qualité devient un challenge intéressant avec un impact applicatif important.

Un moyen pour contourner la NP-complétude est d’exploiter l’information géométrique présente dans ces problèmes. Actuellement, pour résoudre ces problèmes, nous nous tournons vers des heuristiques n’offrant aucune garantie sur le temps d’exécution ainsi que sur la qualité du résultat. Un moyen pour obtenir des approches algorithmiques plus efficaces est d’utiliser des structures de données calculant une approximation des données d’entrée appelée epsilon-nets. Ces structures de données permettant d’éviter de traiter la totalité des données d’entrée tout en garantissant certaines propriétés sur l’écart entre la réalité et l’approximation.

L’objectif de notre projet est de concevoir des solutions algorithmiques apportant une preuve théorique sur leur efficacité comme sur la qualité du résultat obtenu à travers l’étude des approximations de faible taille. Cela nécessite l’analyse des données géométriques (i.e. epsilon-nets) pour construire une structure géométrique approchante (i.e. separators) pour concevoir de nouveaux algorithmes.

Nos objectifs :
- exhiber des structures géométriques pour l’ensemble de nos problèmes
- construire des solutions algorithmiques autour de ces structures
- implémenter nos algorithmes en intégrant des paramètres pour les facteurs d’approximation
- intégrer nos résultats dans une librairie open source

Le responsable principal de ce projet, Nabil Mustafa, possède une expérience dans la construction de solutions algorithmiques pour des problèmes applicatifs à la frontière du monde académique et du monde industriel. Cette expertise est complétée par celle de Claire Mathieu dans l’optimisation des problèmes combinatoires et par celle de Xavier Goaoc dans les structures de données géométriques. Elle se complète par l’expérience de la connaissance de thématiques appliquées avec Frederic Meunier pour l’optimisation et avec Lilian Buzer pour la géométrie.

Ce projet s’inscrit dans un groupe jeune et dynamique avec l’arrivée récente à Paris de Nabil Mustafa et de Claire Mathieu en 2012 et de Xavier Goaoc en 2013. A travers nos échanges, nous avons réalisé le lien existant entre nos spécialités : algorithmiques, géométrie et optimisation.